Problem Statement

We have a grid with 2 horizontal rows and 2 vertical columns.
Each of the squares is black or white, and there are at least 2 black squares.
The colors of the squares are given to you as strings S_1 and S_2, as follows.

• If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left is black.
• If the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is white.

You can travel between two different black squares if and only if they share a side.
Determine whether it is possible to travel from every black square to every black square (directly or indirectly) by only passing black squares.

Constraints

• Each of S_1 and S_2 is a string with two characters consisting of # and ..
• S_1 and S_2 have two or more #s in total.

Sample Input 1

##
.#

Sample Output 1

Yes

It is possible to directly travel between the top-left and top-right black squares and between top-right and bottom-right squares.
These two moves enable us to travel from every black square to every black square, so the answer is Yes.

Sample Input 2

.#
#.

Sample Output 2

No

It is impossible to travel between the top-right and bottom-left black squares, so the answer is No.

Problem Statement

Takahashi is enjoying a game at school. The game starts at the moment the bell rings.

Immediately after the bell rings, he repeats the following actions:

• Run at a speed of S meters per second for A seconds. Then, remain stationary for B seconds.

How many meters in total does he run by the time X seconds have elapsed since the bell rang?

Constraints

• 1 \leq S \leq 15
• 1 \leq A \leq 1000
• 1 \leq B \leq 1000
• 1 \leq X \leq 1000
• All input values are integers.

Sample Input 1

7 3 2 11

Sample Output 1

49

During the 11 seconds after the bell rings, Takahashi moves as follows:

• From 0 seconds to 3 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 21 meters.
• From 3 seconds to 5 seconds, he remains stationary.
• From 5 seconds to 8 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 21 meters.
• From 8 seconds to 10 seconds, he remains stationary.
• From 10 seconds to 11 seconds, he runs at a speed of 7 meters per second. The distance traveled during this time is 7 meters.

The total distance traveled is 49 meters, so output 49.

Sample Input 2

6 3 2 9

Sample Output 2

36

During the 9 seconds after the bell rings, Takahashi moves as follows:

• From 0 seconds to 3 seconds, he runs at a speed of 6 meters per second. The distance traveled during this time is 18 meters.
• From 3 seconds to 5 seconds, he remains stationary.
• From 5 seconds to 8 seconds, he runs at a speed of 6 meters per second. The distance traveled during this time is 18 meters.
• From 8 seconds to 9 seconds, he remains stationary.

The total distance traveled is 36 meters, so output 36.

Sample Input 3

1 1 666 428

Sample Output 3

1

During the 428 seconds after the bell rings, Takahashi moves as follows:

• From 0 seconds to 1 second, he runs at a speed of 1 meter per second. The distance traveled during this time is 1 meter.
• From 1 second to 428 seconds, he remains stationary.

The total distance traveled is 1 meter, so output 1.

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

For a positive integer x, define f(x) as the sum of the digits in the decimal representation of x. For example, f(123) = 1 + 2 + 3 = 6.

Define an infinite sequence A = (A_0, A_1, A_2, \ldots) by the following formula:

• A_0 = 1
• For i \geq 1, A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)

You are given a positive integer N. Find the value of A_N.

Constraints

• N is an integer between 1 and 100, inclusive.

Sample Input 1

6

Sample Output 1

23

• A_0 = 1
• A_1 = f(A_0) = 1
• A_2 = f(A_0) + f(A_1) = 2
• A_3 = f(A_0) + f(A_1) + f(A_2) = 4
• A_4 = f(A_0) + f(A_1) + f(A_2) + f(A_3) = 8
• A_5 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) = 16
• A_6 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) + f(A_5) = 23

Thus, A_6 = 23.

Sample Input 2

45

Sample Output 2

427

Problem Statement

There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).

Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.

Constraints

• 1 \leq N \leq 10^4
• 1 \leq M \leq 7
• 1 \leq B_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

2 3
1 2 3
8 9 10

Sample Output 1

Yes

The given matrix B is the top-left 2 \times 3 submatrix of A.

Sample Input 2

2 1
1
2

Sample Output 2

No

Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.

Sample Input 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

Sample Output 3

Yes

Problem Statement

N students are taking a 4-day exam.

There is a 300-point test on each day, for a total of 1200 points.

The first three days of the exam are already over, and the fourth day is now about to begin. The i-th student (1 \leq i \leq N) got P_{i, j} points on the j-th day (1 \leq j \leq 3).

For each student, determine whether it is possible that he/she is ranked in the top K after the fourth day.
Here, the rank of a student after the fourth day is defined as the number of students whose total scores over the four days are higher than that of the student, plus 1.

Constraints

• 1 \leq K \leq N \leq 10^5
• 0 \leq P_{i, j} \leq 300 \, (1 \leq i \leq N, 1 \leq j \leq 3)
• All values in input are integers.

Sample Input 1

3 1
178 205 132
112 220 96
36 64 20

Sample Output 1

Yes
Yes
No

If every student scores 100 on the fourth day, the 1-st student will rank 1-st.
If the 2-nd student scores 100 and the other students score 0 on the fourth day, the 2-nd student will rank 1-st.
The 3-rd student will never rank 1-st.

Sample Input 2

2 1
300 300 300
200 200 200

Sample Output 2

Yes
Yes

Sample Input 3

4 2
127 235 78
192 134 298
28 56 42
96 120 250

Sample Output 3

Yes
Yes
No
Yes

Problem Statement

There is a directed graph with N vertices and M edges, where vertices are numbered from 1 to N and edges are numbered from 1 to M. Edge i is a directed edge from vertex A_i to vertex B_i with weight W_i.

Find the minimum value of the bitwise \mathrm{XOR} of the weights of edges included in a walk from vertex 1 to vertex N.

Constraints

• 2 \leq N \leq 1000
• 0 \leq M \leq 1000
• 1 \leq A_i,B_i \leq N
• 0 \leq W_i < 2^{10}
• All input values are integers.

Sample Input 1

3 3
1 2 4
2 3 5
1 3 2

Sample Output 1

1

The bitwise \mathrm{XOR} of the weights of edges included in the walk (edge 1, edge 2) is 1.

Sample Input 2

4 4
1 4 7
4 2 2
2 3 4
3 4 1

Sample Output 2

0

The bitwise \mathrm{XOR} of the weights of edges included in the walk (edge 1, edge 2, edge 3, edge 4) is 0.

Note that the walk may include vertex N in the middle.

Sample Input 3

999 4
1 2 9
2 1 8
1 2 7
1 1 6

Sample Output 3

-1

If there is no walk from vertex 1 to vertex N, output -1.

Problem Statement

AtCoder Land sells tiles with English letters written on them. Takahashi is thinking of making a nameplate by arranging these tiles in a row.

Find the number, modulo 998244353, of strings consisting of uppercase English letters with a length between 1 and K, inclusive, that satisfy the following conditions:

• For every integer i satisfying 1 \leq i \leq 26, the following holds:
  • Let a_i be the i-th uppercase English letter in lexicographical order. For example, a_1 = A, a_5 = E, a_{26} = Z.
  • The number of occurrences of a_i in the string is between 0 and C_i, inclusive.

Constraints

• 1 \leq K \leq 1000
• 0 \leq C_i \leq 1000
• All input values are integers.

Sample Input 1

2
2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

10

The 10 strings that satisfy the conditions are A, B, C, AA, AB, AC, BA, BC, CA, CB.

Sample Input 2

358
1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 2

64

Sample Input 3

1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

Sample Output 3

270274035

Problem Statement

You are given N intervals numbered 1 to N. Interval i is [L_i, R_i].

Two intervals [l_a, r_a] and [l_b, r_b] are said to intersect if and only if they satisfy either (l_a < l_b < r_a < r_b) or (l_b < l_a < r_b < r_a).

Define f(l, r) as the number of intervals i (1 \leq i \leq N) that intersect with the interval [l, r].

Among all pairs of integers (l, r) satisfying 0 \leq l < r \leq 10^{9}, find the pair (l, r) that maximizes f(l, r). If there are multiple such pairs, choose the one with the smallest l. If there are still multiple pairs, choose the one with the smallest r among them. (Since 0 \leq l < r, the pair (l, r) to be answered is uniquely determined.)

Constraints

• 1 \leq N \leq 10^{5}
• 0 \leq L_i < R_i \leq 10^{9} (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
1 7
3 9
7 18
10 14
15 20

Sample Output 1

4 11

The maximum value of f(l, r) is 4, and among the pairs (l, r) that achieve f(l, r) = 4, the smallest l is 4. The pairs (l, r) that satisfy f(l, r) = 4 and l = 4 are the following five:

• (l, r) = (4, 11)
• (l, r) = (4, 12)
• (l, r) = (4, 13)
• (l, r) = (4, 16)
• (l, r) = (4, 17)

Among these, the smallest r is 11, so print 4 and 11.

Sample Input 2

11
856977192 996441446
298251737 935869360
396653206 658841528
710569907 929136831
325371222 425309117
379628374 697340458
835681913 939343451
140179224 887672320
375607390 611397526
93530028 581033295
249611310 775998537

Sample Output 2

396653207 887672321