Problem Statement

Print a number between A and B (inclusive) that is a multiple of C.

If there is no such number, print -1.

Constraints

• 1 \leq A \leq B \leq 1000
• 1 \leq C \leq 1000
• All values in input are integers.

Sample Input 1

123 456 100

Sample Output 1

200

300 or 400 would also be accepted.

Sample Input 2

630 940 314

Sample Output 2

-1

Problem Statement

Determine if there is a segment that directly connects the points numbered a and b in the figure below.

Constraints

• 1 \leq a \lt b \leq 15
• a and b are integers.

Sample Input 1

1 2

Sample Output 1

Yes

In the figure in the Problem Statement, there is a segment that directly connects the points numbered 1 and 2, so Yes should be printed.

Sample Input 2

2 8

Sample Output 2

No

In the figure in the Problem Statement, there is no segment that directly connects the points numbered 2 and 8, so No should be printed.

Sample Input 3

14 15

Sample Output 3

No

Problem Statement

You are given an H-by-W matrix A.
The element at the i-th row from the top and j-th column from the left of A is A_{i,j}.

Let B be a W-by-H matrix whose element at the i-th row from the top and j-th column from the left equals A_{j, i}.
That is, B is the transpose of A.

Print B.

Constraints

• 1\leq H,W \leq 10^5
• H \times W \leq 10^5
• 1 \leq A_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

4 3
1 2 3
4 5 6
7 8 9
10 11 12

Sample Output 1

1 4 7 10
2 5 8 11
3 6 9 12

For example, we have A_{2,1}=4, so the element at the 1-st row from the top and 2-nd column from the left of the transpose B is 4.

Sample Input 2

2 2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

1000000000 1000000000
1000000000 1000000000

Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

• 2 \le N \le 100
• 0 \le A_{i,j} \le 1(1 \le i,j \le N)
• All input values are integers.

Sample Input 1

4
0101
1101
1111
0000

Sample Output 1

1010
1101
0111
0001

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

5
01010
01001
10110
00110
01010

Sample Output 3

00101
11000
00111
00110
10100

Problem Statement

You are given patterns S and T consisting of # and ., each with H rows and W columns.
The pattern S is given as H strings, and the j-th character of S_i represents the element at the i-th row and j-th column. The same goes for T.

Determine whether S can be made equal to T by rearranging the columns of S.

Here, rearranging the columns of a pattern X is done as follows.

• Choose a permutation P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
• Then, for every integer i such that 1 \le i \le H, simultaneously do the following.
  • For every integer j such that 1 \le j \le W, simultaneously replace the element at the i-th row and j-th column of X with the element at the i-th row and P_j-th column.

Constraints

• H and W are integers.
• 1 \le H,W
• 1 \le H \times W \le 4 \times 10^5
• S_i and T_i are strings of length W consisting of # and ..

Sample Input 1

3 4
##.#
##..
#...
.###
..##
...#

Sample Output 1

Yes

If you, for instance, arrange the 3-rd, 4-th, 2-nd, and 1-st columns of S in this order from left to right, S will be equal to T.

Sample Input 2

3 3
#.#
.#.
#.#
##.
##.
.#.

Sample Output 2

No

In this input, S cannot be made equal to T.

Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

It is possible that S=T.

Sample Input 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

Sample Output 4

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

There is an online game with N registered players.
Today, which is the 10^{100}-th day since its launch, the developer Takahashi examined the users' login history. It turned out that the i-th player logged in for B_i consecutive days from Day A_i, where Day 1 is the launch day, and did not log in for the other days. In other words, the i-th player logged in on Day A_i, A_i+1, \ldots, A_i+B_i-1, and only on those days.
For each integer k such that 1\leq k\leq N, find the number of days on which exactly k players logged in.

Constraints

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

Sample Input 1

3
1 2
2 3
3 1

Sample Output 1

2 2 0

The first player logged in on Day 1, 2, the second player logged in on Day 2, 3, 4, and the third player logged in on Day 3 only.

Thus, we can see that Day 1, 4 had 1 player logged in, Day 2, 3 had 2 players logged in, and the other days had no players logged in.

The answer is: there were 2 days with exactly 1 player logged in, 2 days with exactly 2 players logged in, and 0 days with exactly 3 players logged in.

Sample Input 2

2
1000000000 1000000000
1000000000 1000000000

Sample Output 2

0 1000000000

There may be two or more players who logged in during the same period.

Problem Statement

There is a H \times W-square 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 grid has a rook, initially on (x_1, y_1). Takahashi will do the following operation K times.

• Move the rook to a square that shares the row or column with the square currently occupied by the rook. Here, it must move to a square different from the current one.

How many ways are there to do the K operations so that the rook will be on (x_2, y_2) in the end? Since the answer can be enormous, find it modulo 998244353.

Constraints

• 2 \leq H, W \leq 10^9
• 1 \leq K \leq 10^6
• 1 \leq x_1, x_2 \leq H
• 1 \leq y_1, y_2 \leq W

Sample Input 1

2 2 2
1 2 2 1

Sample Output 1

2

We have the following two ways.

• First, move the rook from (1, 2) to (1, 1). Second, move it from (1, 1) to (2, 1).
• First, move the rook from (1, 2) to (2, 2). Second, move it from (2, 2) to (2, 1).

Sample Input 2

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

Sample Output 2

24922282

Be sure to find the count modulo 998244353.

Sample Input 3

3 3 3
1 3 3 3

Sample Output 3

9

Problem Statement

There is a tree with N vertices. The 1-st vertex is the root, and the parent of the i-th vertex (2\leq i\leq N) is p _ i\ (1\leq p _ i\lt i).

Each non-root vertex has an enemy or a medicine on it. Takahashi wants to defeat all the enemies. Initially, his strength is 1, and he is at vertex 1. For i=2,\ldots,N, the information of the i-th vertex is represented by a triple of integers (t _ i,s _ i,g _ i) as follows.

• If t _ i=1, there is an enemy at the i-th vertex. When Takahashi visits this vertex for the first time, if his strength is less than s _ i, Takahashi is defeated by the enemy and loses, after which he cannot move to other vertices. Otherwise, he defeats the enemy, and his strength increases by g _ i.
• If t _ i=2, there is a medicine at the i-th vertex. When Takahashi visits this vertex for the first time, he takes the medicine, and his strength is multiplied by g _ i. (For a vertex with a medicine, s _ i=0.)

There are at most 10 vertices with a medicine.

Takahashi can repeatedly move to an adjacent vertex. Determine if he can defeat all the enemies.

Constraints

• 2\leq N\leq 500
• 1\leq p _ i\lt i\ (2\leq i\leq N)
• t _ i\in\lbrace1,2\rbrace\ (2\leq i\leq N)
• t _ i=1\implies1\leq s _ i\leq 10 ^ 9\ (2\leq i\leq N)
• t _ i=2\implies s _ i=0\ (2\leq i\leq N)
• 1\leq g _ i\leq 10 ^ 9\ (2\leq i\leq N)
• There are at most 10 vertices with t _ i=2.
• All input values are integers.

Sample Input 1

8
1 2 0 3
2 1 3 3
1 2 0 4
4 1 2 2
1 2 0 5
6 1 5 5
5 1 140 1

Sample Output 1

Yes

Initially, the tree looks like this:

Takahashi can defeat all the enemies by moving from vertex 1 to 2,3,2,1,6,7,6,1,4,5,8 in this order. Here, his position and strength change as shown in the following figure (movements to vertices that have already been visited are omitted).

On the other hand, if he moves from vertex 1 to 4,5,8 in this order, for example, his strength when visiting vertex 8 will be less than s _ 8=140, so he will lose without defeating all the enemies.

Sample Input 2

12
1 1 166 619
1 1 17 592
2 1 222 983
2 1 729 338
5 1 747 62
3 1 452 815
3 2 0 1
4 2 0 40
4 1 306 520
6 1 317 591
1 1 507 946

Sample Output 2

No

Sample Input 3

12
1 1 1 791
2 2 0 410
2 1 724 790
2 1 828 599
5 2 0 13
3 1 550 803
1 1 802 506
5 1 261 587
6 1 663 329
8 1 11 955
9 1 148 917

Sample Output 3

Yes

Sample Input 4

12
1 2 0 1000000000
2 2 0 1000000000
3 2 0 1000000000
4 2 0 1000000000
5 2 0 1000000000
6 2 0 1000000000
7 2 0 1000000000
8 2 0 1000000000
9 2 0 1000000000
10 2 0 1000000000
11 1 1 1

Sample Output 4

Yes