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

Takahashi and Aoki each have a toy made by attaching M cords to N balls.

In Takahashi's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball A_i and B_i.

Similarly, in Aoki's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball C_i and D_i.

In each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.

Snuke is wondering whether the two toys have the same shape.
Here, they are said to have the same shape when there is a sequence P that satisfies the conditions below.

• P is a permutation of (1, \dots, N).
• For every pair of integers i, j between 1 and N (inclusive), the following holds.
  • Balls i and j in Takahashi's toy are tied by a cord if and only if Balls P_i and P_j in Aoki's toy are tied by a cord.

If the two toys have the same shape, print Yes; otherwise, print No.

Constraints

• 1 \leq N \leq 8
• 0 \leq M \leq \frac{N(N - 1)}{2}
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
• 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
• (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes

Takahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.

The following figure shows that the two toys have the same shape. The condition in the statement is satisfied when P = (3, 2, 1, 4), for example.

Sample Input 2

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

Sample Output 2

No

The two toys do not have the same shape.

Sample Input 3

8 0

Sample Output 3

Yes

Problem Statement

For positive integers x and y, define f(x, y) as follows:

• Interpret the decimal representations of x and y as strings and concatenate them in this order to obtain a string z. The value of f(x, y) is the value of z when interpreted as a decimal integer.

For example, f(3, 14) = 314 and f(100, 1) = 1001.

You are given a sequence of positive integers A = (A_1, \ldots, A_N) of length N. Find the value of the following expression modulo 998244353:

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

3
3 14 15

Sample Output 1

2044

• f(A_1, A_2) = 314
• f(A_1, A_3) = 315
• f(A_2, A_3) = 1415

Thus, the answer is f(A_1, A_2) + f(A_1, A_3) + f(A_2, A_3) = 2044.

Sample Input 2

5
1001 5 1000000 1000000000 100000

Sample Output 2

625549048

Be sure to calculate the value modulo 998244353.

Problem Statement

There are N baskets numbered 1, 2, \ldots, N arranged in a circle.
For each 1\leq i \leq N-1, basket i+1 is to the immediate right of basket i, and basket 1 is to the immediate right of basket N.

Basket i now contains A_i apples.

Takahashi starts in front of basket 1 and repeats the following action.

• If the basket he is facing contains an apple, take one and eat it. Then, regardless of whether he has eaten an apple now, go on to the next basket to the immediate right.

Find the number of apples remaining in each basket when Takahashi has eaten exactly K apples in total.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq A_i \leq 10^{12}
• 1 \leq K \leq 10^{12}
• There are at least K apples in total. That is, \sum_{i=1}^{N}A_i\geq K.
• All values in the input are integers.

Sample Input 1

3 3
1 3 0

Sample Output 1

0 1 0 

Takahashi will do the following.

• Basket 1, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 2. Now, the baskets have 0,3,0 apples.
• Basket 2, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 3. Now, the baskets have 0,2,0 apples.
• Basket 3, which he is facing, contains no apple. Then, he goes on to basket 1. Now, the baskets have 0,2,0 apples.
• Basket 1, which he is facing, contains no apple. Then, he goes on to basket 2. Now, the baskets have 0,2,0 apples.
• Basket 2, which he is facing, contains an apple, so he takes one and eats it. Then, he goes on to basket 3. Now, the baskets have 0,1,0 apple(s).

Sample Input 2

2 1000000000000
1000000000000 1000000000000

Sample Output 2

500000000000 500000000000 

Problem Statement

There is a skating rink represented by a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The skating rink has N obstacles. The i-th obstacle is placed at (X_i,Y_i).

In a single move, Takahashi chooses one of the four directions, up, down, left, or right, and keeps moving until he hits an obstacle.
When he hits an obstacle, he stops at the square right before the obstacle. Since the skating rink is surrounded by cliffs, it is prohibited to start a move in which he will never hit an obstacle.

Takahashi is initially at (s_x,s_y). He wants to make some number of moves to stop at (g_x,g_y).

Find the minimum number of moves required to end up at (g_x, g_y). If it is not possible, report the fact.

Constraints

• 1\leq H \leq 10^9
• 1\leq W \leq 10^9
• 1\leq N \leq 10^5
• 1\leq s_x,g_x\leq H
• 1\leq s_y,g_y\leq W
• 1\leq X_i \leq H
• 1\leq Y_i \leq W
• (s_x,s_y)\neq (g_x,g_y)
• (s_x,s_y)\neq (X_i,Y_i)
• (g_x,g_y)\neq (X_i,Y_i)
• If i\neq j, then (X_i,Y_i)\neq (X_j,Y_j).
• All values in input are integers.

Sample Input 1

7 8 7
3 4
5 6
1 4
2 1
2 8
4 5
5 7
6 2
6 6

Sample Output 1

4

In the figure, (s_x,s_y) is denoted by S and (g_x,g_y) is denoted by G.
By moving as (3,4)\rightarrow(2,4) \rightarrow(2,2) \rightarrow(5,2) \rightarrow(5,6), he can end up at (g_x,g_y) with 4 moves.

Sample Input 2

4 6 2
3 2
3 5
4 5
2 5

Sample Output 2

-1

He must stop at (g_x,g_y).
Note that just passing through (g_x,g_y) is not considered to be ending up at the goal.

Sample Input 3

1 10 1
1 5
1 1
1 7

Sample Output 3

-1

If he chooses to move to the left, Takahashi will fall down the cliff after passing through (g_x,g_y).
Note that it is prohibited to start a move in which he will never hit an obstacle, as the skating rink is surrounded by cliffs.