Problem Statement

Streamer Takahashi has decided to stream from L o'clock to R o'clock (using the 24-hour clock).

He has N listeners, and the i-th listener can watch the stream from X_i o'clock to Y_i o'clock.

How many listeners can watch Takahashi's stream from beginning to end?

Constraints

• 1\leq N\leq 100
• 0\leq L\lt R\leq 23
• 0\leq X_i\lt Y_i\leq 23
• All input values are integers.

Sample Input 1

5 19 22
17 23
20 23
19 22
0 23
12 20

Sample Output 1

3

The listeners who can watch Takahashi's stream from beginning to end are the 1st, 3rd, and 4th listeners.

Sample Input 2

3 12 13
0 1
0 1
0 1

Sample Output 2

0

No listeners can watch Takahashi's stream from beginning to end.

Sample Input 3

10 8 14
5 20
14 21
9 21
5 23
8 10
0 14
3 8
2 6
0 16
5 20

Sample Output 3

5

Problem Statement

Restore run-length encoding. If the result is too long, output Too Long.

You are given N pairs of characters and integers (c_1,l_1),(c_2,l_2),\ldots,(c_N,l_N).

Let S be the string formed by concatenating l_1 characters c_1, l_2 characters c_2, \ldots, and l_N characters c_N in this order.

Output S. However, if the length of S exceeds 100, output Too Long instead.

Constraints

• 1\leq N\leq 100
• 1\leq l_i\leq 10^{18}
• N and l_i are integers.
• Each c_i is a lowercase English letter.
• c_i\neq c_{i+1}

Sample Input 1

8
m 1
i 1
s 2
i 1
s 2
i 1
p 2
i 1

Sample Output 1

mississippi

S is mississippi. Since the length of S is not greater than 100, output S.

Sample Input 2

7
a 1000000000000000000
t 1000000000000000000
c 1000000000000000000
o 1000000000000000000
d 1000000000000000000
e 1000000000000000000
r 1000000000000000000

Sample Output 2

Too Long

The length of S is 7\times 10^{18}, so output Too Long.

Sample Input 3

1
a 100

Sample Output 3

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Input 4

6
g 4
j 1
m 4
e 4
d 3
i 4

Sample Output 4

ggggjmmmmeeeedddiiii

Problem Statement

The decimal representation of 414 is 414, which is a palindrome. Also, the octal representation of 414 is 636, which is also a palindrome. Based on this, solve the following problem.

You are given positive integers A and N. Find the sum of all integers between 1 and N, inclusive, whose decimal representation and base-A representation are both palindromes.

Under the constraints of this problem, it can be proved that the answer is less than 2^{63}.

Constraints

• 2 \leq A \leq 9
• 1 \leq N \le 10^{12}
• All input values are integers.

Sample Input 1

8
1000

Sample Output 1

2155

The integers satisfying the condition are 1,2,3,4,5,6,7,9,121,292,333,373,414,585 (14 integers), and their sum is 2155.

Sample Input 2

8
999999999999

Sample Output 2

914703021014

Sample Input 3

6
999999999999

Sample Output 3

283958331810

Problem Statement

There are N houses numbered from 1 to N on a number line. House i is located at coordinate X_i. Multiple houses may be located at the same coordinate.

You place M base stations at arbitrary real coordinates on the number line. Then, you set a non-negative integer signal strength for each base station.

When the signal strength of a base station is set to x, The signal from that base station reaches a house if and only if the distance between the base station and the house is at most \displaystyle\frac{x}{2}. Particularly, when x=0, the signal reaches only houses located at the same coordinate as the base station.

Find the minimum possible sum of signal strengths when the positions and signal strengths of the base stations are set such that at least one base station's signal reaches every house.

It can be proved that the answer is an integer for any input satisfying the constraints.

Constraints

• 1 \leq M \leq N \leq 5 \times 10^5
• 1 \leq X_i \leq 10^{12} (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

7 3
5 10 15 20 8 14 15

Sample Output 1

6

By placing three base stations as follows, signals reach all houses.

• Place a base station with signal strength 5 at coordinate 7.5. This base station reaches houses 1,2,5.
• Place a base station with signal strength 1 at coordinate 14.5. This base station reaches houses 3,6,7.
• Place a base station with signal strength 0 at coordinate 20. This base station reaches house 4.

The sum of signal strengths in this case is 6.

It is impossible to satisfy the condition with an arrangement where the sum of signal strengths is smaller than 6, so output 6.

Sample Input 2

7 7
5 10 15 20 8 14 15

Sample Output 2

0

Sample Input 3

7 1
5 10 15 20 8 14 15

Sample Output 3

15

Problem Statement

Find the number, modulo 998244353, of integer tuples (a, b, c) that satisfy the following conditions.

• 1 \leq a,b,c \leq N
• a,b,c are pairwise distinct.
• The remainder when a is divided by b is equal to c.

Constraints

• 3 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

7

Sample Output 1

12

There are 12 integer tuples (a,b,c) that satisfy the conditions:

• (3,2,1)
• (4,3,1)
• (5,2,1)
• (5,3,2)
• (5,4,1)
• (6,4,2)
• (6,5,1)
• (7,2,1)
• (7,3,1)
• (7,4,3)
• (7,5,2)
• (7,6,1)

Sample Input 2

441

Sample Output 2

94700

Sample Input 3

411111111114

Sample Output 3

462474062

Problem Statement

You are given a tree with N vertices numbered from 1 to N and an integer K. The i-th edge bidirectionally connects vertices u_i and v_i.

You are currently at vertex 1. You can repeat the following operation zero or more times:

• Choose a vertex whose distance from the vertex you are currently at is K, and move to that vertex. Here, the distance between two vertices is the number of edges in the simple path connecting the two vertices.

For each k=2,\ldots,N, determine whether you can move to vertex k by repeating the operation, and if you can move, find the minimum number of operations.

You have T test cases, so solve each of them.

Constraints

• 1\leq T\leq 10^5
• 2\leq N\leq 2\times 10^5
• 1\leq K\leq 20
• 1\leq u_i\lt v_i\leq N
• The given graph is a tree.
• The sum of N over all test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

1
6 2
1 2
2 3
2 4
4 5
5 6

Sample Output 1

-1 1 1 -1 2

This sample input/output consists of one test case.

The vertices whose distance from vertex 1 is 2 are vertices 3 and 4, so you can move to these two vertices with one operation.

Also, by moving from vertex 1 to vertex 4, then moving to vertex 6 whose distance from vertex 4 is 2, you can move to vertex 6 with two operations.

You cannot move to vertices 2 and 5 no matter how you perform the operations.

Sample Input 2

3
2 20
1 2
10 2
1 9
1 8
1 5
6 8
4 5
2 8
5 10
7 9
3 5
10 1
2 6
2 9
8 9
9 10
3 9
4 9
7 9
1 6
3 5

Sample Output 2

-1
1 1 1 -1 1 1 -1 -1 1
2 4 4 5 1 4 4 3 4

Problem Statement

In AtCoder Kingdom, there is a railway line extending east-west, and this line has stations 1,2,\ldots,N. Station i\ (1\leq i\leq N) is located at coordinate x_i (x_1 < x_2 < \ldots < x_N).

On this line, AtCoder Express company operates M types of express trains.

The i-th type of express train operates as follows:

• You can board this train at one of the stations l_i,l_i+1,\ldots,r_i.
• You can get off this train at one of the stations L_i, L_i+1, \ldots, R_i. Here, the train travels in one direction, either east or west, satisfying r_i\lt L_i or R_i\lt l_i.
• The fare consists of a base fare of c_i plus an amount based on the distance from the boarding station to the destination station. Specifically, when traveling from station s\ (l_i\leq s\leq r_i) to station t\ (L_i\leq t\leq R_i), the fare is c_i+|x_s-x_t|.

You are currently at station 1. For each k\ (2\leq k\leq N), determine whether you can travel from station 1 to station k by transferring between express trains, and if you can travel, find the minimum total fare required for the travel.

Constraints

• 2\leq N\leq 10^5
• 1\leq M\leq 10^5
• 0\leq x_1 < x_2 < \ldots < x_N \leq 10^{12}
• 1\leq l_i\leq r_i\leq N, 1\leq L_i\leq R_i\leq N
• r_i\lt L_i or R_i\lt l_i.
• 1\leq c_i\leq 10^{12}
• All input values are integers.

Sample Input 1

6 3
0 20 50 90 110 150
1 2 5 6 100
1 1 2 3 10000
6 6 1 2 30

Sample Output 1

410 10050 -1 210 250

You can travel to station 2 as follows:

1. Board the 1st express train at station 1 and get off at station 6. The fare is c_1+|x_1-x_6|=100+|0-150|=250.
2. Board the 3rd express train at station 6 and get off at station 2. The fare is c_3+|x_6-x_2|=30+|150-20|=160.

The total fare in this case is 410, which is the minimum.

You cannot travel to station 4.

Sample Input 2

10 5
4427 6839 17992 39701 46954 76602 81804 91814 95651 95895
3 4 10 10 60978
1 1 4 4 30037
9 10 7 8 66643
4 4 1 2 50872
8 10 3 7 23949

Sample Output 2

149045 284335 65311 255373 225725 220523 253207 -1 182483