Problem Statement

We have the following 3 \times 3 board with integers from 1 through 9 written on it.

You are given two integers A and B between 1 and 9, where A < B.

Determine if the two squares with A and B written on them are adjacent horizontally.

Constraints

• 1 \le A < B \le 9
• A and B are integers.

Sample Input 1

7 8

Sample Output 1

Yes

The two squares with 7 and 8 written on them are adjacent horizontally, so print Yes.

Sample Input 2

1 9

Sample Output 2

No

Sample Input 3

3 4

Sample Output 3

No

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

Snuke the doctor prescribed N kinds of medicine for Takahashi. For the next a_i days (including the day of the prescription), he has to take b_i pills of the i-th medicine. He does not have to take any other medicine.

Let the day of the prescription be day 1. On or after day 1, when is the first day on which he has to take K pills or less?

Constraints

• 1 \leq N \leq 3 \times 10^5
• 0 \leq K \leq 10^9
• 1 \leq a_i,b_i \leq 10^9
• All input values are integers.

Sample Input 1

4 8
6 3
2 5
1 9
4 2

Sample Output 1

3

On day 1, he has to take 3,5,9, and 2 pills of the 1-st, 2-nd, 3-rd, and 4-th medicine, respectively. In total, he has to take 19 pills on this day, which is not K(=8) pills or less.
On day 2, he has to take 3,5, and 2 pills of the 1-st, 2-nd, and 4-th medicine, respectively. In total, he has to take 10 pills on this day, which is not K(=8) pills or less.
On day 3, he has to take 3 and 2 pills of the 1-st and 4-th medicine, respectively. In total, he has to take 5 pills on this day, which is K(=8) pills or less for the first time.

Thus, the answer is 3.

Sample Input 2

4 100
6 3
2 5
1 9
4 2

Sample Output 2

1

Sample Input 3

15 158260522
877914575 2436426
24979445 61648772
623690081 33933447
476190629 62703497
211047202 71407775
628894325 31963982
822804784 50968417
430302156 82631932
161735902 80895728
923078537 7723857
189330739 10286918
802329211 4539679
303238506 17063340
492686568 73361868
125660016 50287940

Sample Output 3

492686569

Problem Statement

We have an undirected graph with (N_1+N_2) vertices and M edges. For i=1,2,\ldots,M, the i-th edge connects vertex a_i and vertex b_i.
The following properties are guaranteed:

• Vertex u and vertex v are connected, for all integers u and v with 1 \leq u,v \leq N_1.
• Vertex u and vertex v are connected, for all integers u and v with N_1+1 \leq u,v \leq N_1+N_2.
• Vertex 1 and vertex (N_1+N_2) are disconnected.

Consider performing the following operation exactly once:

• choose an integer u with 1 \leq u \leq N_1 and an integer v with N_1+1 \leq v \leq N_1+N_2, and add an edge connecting vertex u and vertex v.

We can show that vertex 1 and vertex (N_1+N_2) are always connected in the resulting graph; so let d be the minimum length (number of edges) of a path between vertex 1 and vertex (N_1+N_2).

Find the maximum possible d resulting from adding an appropriate edge to add.

Constraints

• 1 \leq N_1,N_2 \leq 1.5 \times 10^5
• 0 \leq M \leq 3 \times 10^5
• 1 \leq a_i \leq b_i \leq N_1+N_2
• (a_i,b_i) \neq (a_j,b_j) if i \neq j.
• Vertex u and vertex v are connected for all integers u and v such that 1 \leq u,v \leq N_1.
• Vertex u and vertex v are connected for all integers u and v such that N_1+1 \leq u,v \leq N_1+N_2.
• Vertex 1 and vertex (N_1+N_2) are disconnected.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

If we set u=2 and v=5, the operation yields d=5, which is the maximum possible.

Sample Input 2

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

Sample Output 2

4

Problem Statement

There is a family consisting of person 1, person 2, \ldots, and person N. For i\geq 2, person i's parent is person p_i.

They bought insurance M times. For i=1,2,\ldots,M, person x_i bought the i-th insurance, which covers that person and their descendants in the next y_i generations.

How many people are covered by at least one insurance?

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq M \leq 3 \times 10^5
• 1 \leq p_i \leq i-1
• 1 \leq x_i \leq N
• 1 \leq y_i \leq 3 \times 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

The 1-st insurance covers people 1, 2, and 4, because person 1's 1-st generation descendants are people 2 and 4.
The 2-nd insurance covers people 1, 2, 3, and 4, because person 1's 1-st generation descendants are people 2 and 4, and person 1's 2-nd generation descendant is person 3.
The 3-rd insurance covers person 4, because person 4 has no 1-st, 2-nd, or 3-rd descendants.

Therefore, four people, people 1, 2, 3, and 4, are covered by at least one insurance.

Sample Input 2

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

Sample Output 2

10

Problem Statement

There are N boxes. The i-th box has a shape of a rectangular cuboid whose height, width, and depth are h_i,w_i, and d_i, respectively.

Determine if there are two boxes such that one's height, width, and depth are strictly greater than those of the other after rotating them if necessary.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq h_i,w_i,d_i \leq 10^9
• All input values are integers.

Sample Input 1

3
19 8 22
10 24 12
15 25 11

Sample Output 1

Yes

If you rotate the 2-nd box to swap its height and depth, the 3-rd box will have greater height, depth, and width.

Sample Input 2

3
19 8 22
10 25 12
15 24 11

Sample Output 2

No

Sample Input 3

2
1 1 2
1 2 2

Sample Output 3

No

Problem Statement

Find the number, modulo 998244353, of permutations P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N) such that:

• |P_i - i| \ge X for all integers i with 1 \le i \le N.

Constraints

• 1 \le N \le 100
• 1 \le X \le 5
• All input values are integers.

Sample Input 1

3 1

Sample Output 1

2

The conforming permutations P=(P_1,P_2,P_3) are the following two, (2,3,1) and (3,1,2), so the answer is 2.

Sample Input 2

5 2

Sample Output 2

4

Sample Input 3

98 5

Sample Output 3

809422418

Problem Statement

We have a grid with N rows and M columns. We denote by (i,j) the cell in the i-th row from the top and j-th column from the left.

You are given integer sequences A=(A_1,A_2,\dots,A_K) and B=(B_1,B_2,\dots,B_L) of lengths K and L, respectively.

Find the sum, modulo 998244353, of the answers to the following question over all integer pairs (i,j) such that 1 \le i \le K and 1 \le j \le L.

• A piece is initially placed at (1,A_i). How many paths are there to take it to (N,B_j) by repeating the following move (N-1) times?
  • Let (p,q) be the piece's current cell. Move it to (p+1,q-1),(p+1,q), or (p+1,q+1), without moving it outside the grid.

Constraints

• 1 \le N \le 10^9
• 1 \le M,K,L \le 10^5
• 1 \le A_i,B_j \le M

Sample Input 1

3 4 1 2
1
1 2

Sample Output 1

4

For (i,j)=(1,1), the following two paths are possible:

• (1,1) \rightarrow (2,1) \rightarrow (3,1)
• (1,1) \rightarrow (2,2) \rightarrow (3,1)

For (i,j)=(1,2), the following two paths are possible:

• (1,1) \rightarrow (2,1) \rightarrow (3,2)
• (1,1) \rightarrow (2,2) \rightarrow (3,2)

Thus, the answer is 2 + 2 =4.

Sample Input 2

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

Sample Output 2

137

Sample Input 3

883671387 87719 10 12
86879 64174 47274 41688 17713 50897 53989 7210 30894 5714
60358 28835 48036 48450 67149 36558 35929 69025 77539 19195 60762 60721

Sample Output 3

941873621