Problem Statement

There is an ultramarathon course totaling 100\;\mathrm{km}. Water stations are set up every 5\;\mathrm{km} along the course, including the start and goal, for a total of 21.

Takahashi is at the N\;\mathrm{km} point of this course. Find the position of the nearest water station to him.

Under the constraints of this problem, it can be proven that the nearest water station is uniquely determined.

Constraints

• 0\leq N\leq100
• N is an integer.

Sample Input 1

53

Sample Output 1

55

Takahashi is at the 53\;\mathrm{km} point of the course. The water station at the 55\;\mathrm{km} point is 2\;\mathrm{km} away, and there is no closer water station. Therefore, you should print 55.

Sample Input 2

21

Sample Output 2

20

Takahashi could also go back the way.

Sample Input 3

100

Sample Output 3

100

There are also water stations at the start and goal. Additionally, Takahashi may already be at a water station.

Problem Statement

You are given N integers A_1, A_2, \dots, A_N. Also, define B_i = A_i \times A_{i+1}\ (1 \leq i \leq N-1).

Print B_1, B_2, \dots, B_{N-1} in this order, separated by spaces.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

3
3 4 6

Sample Output 1

12 24

We have B_1 = A_1 \times A_2 = 12, B_2 = A_2 \times A_3 = 24.

Sample Input 2

5
22 75 26 45 72

Sample Output 2

1650 1950 1170 3240

Problem Statement

You are given a positive integer N. If there are integers x and y such that N=2^x3^y, print Yes; otherwise, print No.

Constraints

• 1\leq N\leq10^{18}
• N is an integer.

Sample Input 1

324

Sample Output 1

Yes

For x=2,y=4, we have 2^x3^y=2^23^4=4\times81=324, so the condition is satisfied. Thus, you should print Yes.

Sample Input 2

5

Sample Output 2

No

There are no integers x and y such that 2^x3^y=5. Thus, you should print No.

Sample Input 3

32

Sample Output 3

Yes

For x=5,y=0, we have 2^x3^y=32\times1=32, so you should print Yes.

Sample Input 4

37748736

Sample Output 4

Yes

Problem Statement

There are N sequences of integers.
The i-th (1 \leq i \leq N) sequence has L_i terms; the j-th (1 \leq j \leq L_i) term of the i-th sequence is a_{i, j}.

You are given Q queries. For the k-th (1 \leq k \leq Q) query, given integers s_k and t_k, find the t_k-th term of the s_k-th sequence.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• L_i \geq 1 \, (1 \leq i \leq N)
• \sum_{i=1}^N L_i \leq 2 \times 10^5
• 1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
• 1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

7
5

The 1-st sequence is (1, 4, 7) and the 2-nd is (5, 9).
The answer to each query is as follows:

• The 3-rd term of the 1-st sequence is 7.
• The 1-st term of the 2-nd sequence is 5.

Sample Input 2

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

Sample Output 2

128
1
26535
901

Problem Statement

Takahashi has created a game where the player controls a dragon on a coordinate plane.

The dragon consists of N parts numbered 1 to N, with part 1 being called the head.

Initially, part i is located at the coordinates (i,0). Process Q queries as follows.

• 1 C: Move the head by 1 in direction C. Here, C is one of R, L, U, and D, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.
• 2 p: Find the coordinates of part p.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq Q \leq 2\times 10^5
• For the first type of query, C is one of R, L, U, and D.
• For the second type of query, 1\leq p \leq N.
• All numerical input values are integers.

Sample Input 1

5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5

Sample Output 1

3 0
2 0
1 1
1 0
1 0

At each time when processing the second type of query, the parts are at the following positions:

Note that multiple parts may exist at the same coordinates.

Problem Statement

You are given a string S of length N consisting only of lowercase English letters.

Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.

Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.

Constraints

• 2 \leq K \leq N \leq 10
• N and K are integers.
• S is a string of length N consisting only of lowercase English letters.

Sample Input 1

3 2
aab

Sample Output 1

1

The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.

Sample Input 2

5 3
zzyyx

Sample Output 2

16

There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.

Sample Input 3

10 5
abcwxyzyxw

Sample Output 3

440640

Problem Statement

There are N dice. The i-th die has K_i faces, with the numbers A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} written on them. When you roll this die, each face appears with probability \frac{1}{K_i}.

You choose two dice from the N dice and roll them. Determine the maximum probability that the two dice show the same number, when the dice are chosen optimally.

Constraints

• 2 \leq N \leq 100
• 1 \leq K_i
• K_1 + K_2 + \dots + K_N \leq 10^5
• 1 \leq A_{i,j} \leq 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

0.333333333333333

• When choosing the 1st and 2nd dice, the probability that the outcomes are the same is \frac{1}{3}.
• When choosing the 1st and 3rd dice, the probability is \frac{1}{6}.
• When choosing the 2nd and 3rd dice, the probability is \frac{1}{6}.

Therefore, the maximum probability is \frac{1}{3} = 0.3333333333\ldots.

Sample Input 2

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

Sample Output 2

0.666666666666667

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

Perform the following operation M times:

• For each i\ (1\leq i \leq N), add i to A_i. Then, find the minimum non-negative integer not contained in A.

Constraints

• 1\leq N,M \leq 2\times 10^5
• -10^9\leq A_i\leq 10^9
• All values in the input are integers.

Sample Input 1

3 3
-1 -1 -6

Sample Output 1

2
2
0

The 1-st operation makes the sequence A

(-1 + 1, -1 +2 ,-6+3) = (0,1,-3).

The minimum non-negative integer not contained in A is 2.

The 2-nd operation makes the sequence A

(0 + 1, 1 +2 ,-3+3) = (1,3,0).

The minimum non-negative integer not contained in A is 2.

The 3-rd operation makes the sequence A

(1 + 1, 3 +2 ,0+3) = (2,5,3).

The minimum non-negative integer not contained in A is 0.

Sample Input 2

5 6
-2 -2 -5 -7 -15

Sample Output 2

1
3
2
0
0
0

Problem Statement

We have a grid with N rows and M columns. The square (i,j) at the i-th row from the top and j-th column from the left has an integer (i-1) \times M + j written on it.
Let us perform the following operation on this grid.

• For every square (i,j) such that i+j is odd, replace the integer on that square with 0.

Answer Q questions on the grid after the operation.
The i-th question is as follows:

• Find the sum of the integers written on all squares (p,q) that satisfy all of the following conditions, modulo 998244353.
  • A_i \le p \le B_i.
  • C_i \le q \le D_i.

Constraints

• All values in the input are integers.
• 1 \le N,M \le 10^9
• 1 \le Q \le 2 \times 10^5
• 1 \le A_i \le B_i \le N
• 1 \le C_i \le D_i \le M

Sample Input 1

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

Sample Output 1

28
27
36
14
0
104

The grid in this input is shown below.

This input contains six questions.

• The answer to the first question is 0+3+0+6+0+8+0+11+0=28.
• The answer to the second question is 1+0+9+0+17=27.
• The answer to the third question is 17+0+19+0=36.
• The answer to the fourth question is 14.
• The answer to the fifth question is 0.
• The answer to the sixth question is 104.

Sample Input 2

1000000000 1000000000
3
1000000000 1000000000 1000000000 1000000000
165997482 306594988 719483261 992306147
1 1000000000 1 1000000000

Sample Output 2

716070898
240994972
536839100

For the first question, note that although the integer written on the square (10^9,10^9) is 10^{18}, you are to find it modulo 998244353.

Sample Input 3

999999999 999999999
3
999999999 999999999 999999999 999999999
216499784 840031647 84657913 415448790
1 999999999 1 999999999

Sample Output 3

712559605
648737448
540261130