Problem Statement

Takahashi turns on the light of his room at S o'clock (on the 24-hour clock) every day and turns it off at T o'clock every day.
The date may change while the light is on.

Determine whether the light is on at 30 minutes past X o'clock.

Constraints

• 0 \leq S, T, X \leq 23
• S \neq T
• All values in input are integers.

Sample Input 1

7 20 12

Sample Output 1

Yes

The light is on between 7 o'clock and 20 o'clock. At 30 minutes past 12 o'clock, it is on, so we print Yes.

Sample Input 2

20 7 12

Sample Output 2

No

The light is on between 0 o'clock and 7 o'clock, and between 20 o'clock and 0 o'clock (on the next day). At 30 minutes past 12 o'clock, it is off, so we print No.

Sample Input 3

23 0 23

Sample Output 3

Yes

Problem Statement

Takahashi has N friends. They have nicknames: Friend 1, Friend 2, \ldots, Friend N.

One day, Takahashi accidentally let one of his friends, Friend X, learn his shameful secret.
For each i = 1, 2, \ldots, N, when Friend i learns the secret, he/she will share it with Friend A_i, if Friend A_i has not already learned it.

How many of Takahashi's friends will learn the secret in the end?

Constraints

• 2 \leq N \leq 10^5
• 1 \leq X \leq N
• 1 \leq A_i \leq N
• A_i \neq i
• All values in input are integers.

Sample Input 1

4 2
3 1 1 2

Sample Output 1

3

Takahashi's secret will be learned by Friend 1, Friend 2, and Friend 3, as follows.

• One day, Takahashi let Friend 2 learn the secret.
• Friend 2 shares it with Friend 1.
• Friend 1 shares it with Friend 3.

In the end, three of his friends learn the secret, so we print 3.

Sample Input 2

20 12
7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10

Sample Output 2

7

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 sequence A = (A_0, A_1, \dots, A_{N - 1}) with N = 2^{20} terms. Initially, every term is -1.

Process Q queries in order. The i-th query (1 \leq i \leq Q) is described by an integer t_i such that t_i = 1 or t_i = 2, and another integer x_i, as follows.

• If t_i = 1, do the following in order.
  1. Define an integer h as h = x_i.
  2. While A_{h \bmod N} \neq -1, keep adding 1 to h. We can prove that this process ends after finite iterations under the Constraints of this problem.
  3. Replace the value of A_{h \bmod N} with x_i.
• If t_i = 2, print the value of A_{x_i \bmod N} at that time.

Here, for integers a and b, a \bmod b denotes the remainder when a is divided by b.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• t_i \in \{ 1, 2 \} \, (1 \leq i \leq Q)
• 0 \leq x_i \leq 10^{18} \, (1 \leq i \leq Q)
• There is at least one i (1 \leq i \leq Q) such that t_i = 2.
• All values in input are integers.

Sample Input 1

4
1 1048577
1 1
2 2097153
2 3

Sample Output 1

1048577
-1

We have x_1 \bmod N = 1, so the first query sets A_1 = 1048577.

In the second query, initially we have h = x_2, for which A_{h \bmod N} = A_{1} \neq -1, so we add 1 to h. Now we have A_{h \bmod N} = A_{2} = -1, so this query sets A_2 = 1.

In the third query, we print A_{x_3 \bmod N} = A_{1} = 1048577.

In the fourth query, we print A_{x_4 \bmod N} = A_{3} = -1.

Note that, in this problem, N = 2^{20} = 1048576 is a constant and not given in input.

Problem Statement

Integer Sequence Exhibition is taking place, where integer sequences are gathered in one place and evaluated. Here, every integer sequence of length N consisting of integers between 1 and K (inclusive) is evaluated and given an integer score between 1 and M (inclusive).

Print the number, modulo 998244353, of ways to give each of the evaluated sequences a score between 1 and M.

Here, two ways are said to be different when there is an evaluated sequence A = (A_1, A_2, \ldots, A_N) that is given different scores by the two ways.

Constraints

• 1 \leq N, K, M \leq 10^{18}
• N, K, and M are integers.

Sample Input 1

2 2 2

Sample Output 1

16

Four sequences are evaluated: (1, 1), (1, 2), (2, 1), and (2, 2). There are 16 ways to give each of these sequences a score between 1 and 2, as follows.

• Give 1 to (1, 1), 1 to (1, 2), 1 to (2, 1), and 1 to (2, 2)
• Give 1 to (1, 1), 1 to (1, 2), 1 to (2, 1), and 2 to (2, 2)
• Give 1 to (1, 1), 1 to (1, 2), 2 to (2, 1), and 1 to (2, 2)
• Give 1 to (1, 1), 1 to (1, 2), 2 to (2, 1), and 2 to (2, 2)
• \cdots
• Give 2 to (1, 1), 2 to (1, 2), 2 to (2, 1), and 2 to (2, 2)

Thus, we print 16.

Sample Input 2

3 14 15926535

Sample Output 2

109718301

Be sure to print the count modulo 998244353.

Problem Statement

There is 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.
For each pair of integers (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, (i, j) contains a positive integer A_{i,j}. Additionally, every square is painted white.

Takahashi has a rectangular black stamp that can cover h_1 rows and w_1 columns, and Aoki has a rectangular white stamp that can cover h_2 rows and w_2 columns. Using these stamps and the grid, they will play a game against each other.

First, Takahashi presses his black stamp to paint a rectangular region with h_1 rows and w_1 columns black.
That is, he chooses a pair of integers (i, j) such that 1 \leq i \leq H - h_1 + 1 and 1 \leq j \leq W - w_1 + 1, and paints black every square (r, c) such that i \leq r \leq i + h_1 - 1 and j \leq c \leq j + w_1 - 1.

Second, Aoki presses his white stamp to paint a rectangular region with h_2 rows and w_2 columns white.
That is, he chooses a pair of integers (i, j) such that 1 \leq i \leq H - h_2 + 1 and 1 \leq j \leq W - w_2 + 1, and paints white every square (r, c) such that i \leq r \leq i + h_2 - 1 and j \leq c \leq j + w_2 - 1.
If some of these squares are already painted black by Takahashi, they will also become white.

The game's score is defined as the sum of the integers written on the squares painted black after Takahashi and Aoki press their stamps as described above. Takahashi follows the optimal strategy to make the score as large as possible, while Aoki follows the optimal strategy to make the score as small as possible. What will the game's score be?

Constraints

• 2 \leq H, W \leq 1000
• 1 \leq h_1, h_2 \leq H
• 1 \leq w_1, w_2 \leq W
• 1 \leq A_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

19

The game will go as follows.

• Initially, all squares are painted white.
• First, Takahashi presses his 2 \times 3 black stamp to paint the following six squares black: (2, 2), (2, 3), (2 ,4), (3, 2), (3, 3), (3, 4).
• Second, Aoki presses his 3 \times 1 white stamp to paint the following three squares white: (1, 4), (2, 4), (3, 4).
• Eventually, the following four squares are painted black: (2, 2), (2, 3), (3, 2), (3, 3), for a score of 9 + 2 + 3 + 5 = 19.

Sample Input 2

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

Sample Output 2

0

After Aoki presses his stamp, all squares will be white, for a score of 0.

Sample Input 3

10 10 3 7 2 3
9 7 19 7 10 4 13 9 4 8
10 15 16 3 18 19 17 12 13 2
12 18 4 9 13 13 6 13 5 2
16 12 2 14 18 17 14 7 8 12
12 13 17 12 14 15 19 7 13 15
5 2 16 10 4 6 1 2 7 8
10 14 14 10 9 13 11 4 9 19
16 12 3 19 19 6 2 19 14 20
15 3 19 19 2 10 1 4 3 15
13 20 5 6 19 1 7 17 10 19

Sample Output 3

180

Problem Statement

There is a grid with H horizontal rows and W vertical columns, where each square contains a digit between 1 and 9. For each pair of integers (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, the digit written on the square at the i-th row from the top and j-th column from the left is c_{i, j}.

Using this grid, Takahashi and Aoki will play together. First, Takahashi chooses a square and puts a piece on it. Then, the two will repeat the following procedures, 1. through 4., N times.

1. Takahashi does one of the following two actions.
   • Move the piece to another square that shares a row with the square the piece is on.
   • Do nothing.
2. Takahashi writes on a blackboard the digit written on the square the piece is on.
3. Aoki does one of the following two actions.
   • Move the piece to another square that shares a column with the square the piece is on.
   • Do nothing.
4. Aoki writes on the blackboard the digit written on the square the piece is on.

After that, there will be 2N digits written on the blackboard. Let d_1, d_2, \ldots, d_{2N} be those digits, in the order they are written. The two boys will concatenate the 2N digits in this order to make a 2N-digit integer X := d_1d_2\ldots d_{2N}.

Find the number, modulo 998244353, of different integers that X can become.

Constraints

• 2 \leq H, W \leq 10
• 1 \leq N \leq 300
• 1 \leq c_{i, j} \leq 9
• All values in input are integers.

Sample Input 1

2 2 1
31
41

Sample Output 1

5

Below is one possible scenario.

• First, Takahashi puts the piece on (1, 2).
• Takahashi moves the piece from (1, 2) to (1, 1), and then writes the digit 3 written on (1, 1).
• Aoki moves the piece from (1, 1) to (2, 1), and then writes the digit 4 written on (2, 1).

In this case, we have X = 34.
Below is another possible scenario.

• First, Takahashi puts the piece on (2, 2).
• Takahashi keeps the piece on (2, 2), and then writes the digit 1 written on (2, 2).
• Aoki moves the piece from (2, 2) to (1, 2), and then writes the digit 1 written on (1, 2).

In this case, we have X = 11. Other than these, X can also become 33, 44, or 43, but nothing else.
That is, there are five integers that X can become, so we print 5.

Sample Input 2

2 3 4
777
777

Sample Output 2

1

X can only become 77777777.

Sample Input 3

10 10 300
3181534389
4347471911
4997373645
5984584273
1917179465
3644463294
1234548423
6826453721
5892467783
1211598363

Sample Output 3

685516949

Be sure to find the count modulo 998244353.

Problem Statement

Given are integer sequences of length N each: A = (A_1, \dots, A_N) and C = (C_1, \dots, C_N).

You can do the following operation any number of times, possibly zero.

• Choose an integer i such that 1 \leq i \leq N and add 1 to the value of A_i, for a cost of C_i yen (Japanese currency).

After you are done with the operation, you have to pay K \times X yen, where K is the number of different values among the elements of A.

What is the minimum total amount of money you have to pay?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq X \leq 10^6
• 1 \leq A_i, C_i \leq 10^6 \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

3 5
3 2
2 4
4 3

Sample Output 1

12

After adding 1 to A_1, there will be two different values among the elements of A, for a total cost of C_1 + 2 \times X = 12 yen. It is impossible to make the total cost less than this.

Sample Input 2

1 1
1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

29