Problem Statement

A function f(x) defined for non-negative integer x satisfies the following conditions:

• f(0) = 1;
• f(k) = k \times f(k-1) for all positive integers k.

Find f(N).

Constraints

• N is an integer such that 0 \le N \le 10.

Sample Input 1

2

Sample Output 1

2

We have f(2) = 2 \times f(1) = 2 \times 1 \times f(0) = 2 \times 1 \times 1 = 2.

Sample Input 2

3

Sample Output 2

6

We have f(3) = 3 \times f(2) = 3 \times 2 = 6.

Sample Input 3

0

Sample Output 3

1

Sample Input 4

10

Sample Output 4

3628800

Problem Statement

You are given two integers A and B, each between 0 and 9, inclusive.

Print any integer between 0 and 9, inclusive, that is not equal to A + B.

Constraints

• 0 \leq A \leq 9
• 0 \leq B \leq 9
• A + B \leq 9
• A and B are integers.

Sample Input 1

2 5

Sample Output 1

2

When A = 2, B = 5, we have A + B = 7. Thus, printing any of 0, 1, 2, 3, 4, 5, 6, 8, 9 is correct.

Sample Input 2

0 0

Sample Output 2

9

Sample Input 3

7 1

Sample Output 3

4

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 weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:

• We can choose at most 3 different weights so that they have a total mass of n.

How many positive integers less than or equal to W are good integers?

Constraints

• 1 \leq N \leq 300
• 1 \leq W \leq 10^6
• 1 \leq A_i \leq 10^6
• All values in input are integers.

Sample Input 1

2 10
1 3

Sample Output 1

3

If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.

Sample Input 2

2 1
2 3

Sample Output 2

0

There are no good integers less than or equal to W.

Sample Input 3

4 12
3 3 3 3

Sample Output 3

3

There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.

Sample Input 4

7 251
202 20 5 1 4 2 100

Sample Output 4

48

Problem Statement

Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.

You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.

• First, choose one real number x.
• Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.

What is the maximum number of gifts you can acquire?

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le M \le 10^9
• 0 \le A_i \le 10^9

Sample Input 1

8 6
2 3 5 7 11 13 17 19

Sample Output 1

4

For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.

Sample Input 2

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

Sample Output 2

2

There may be multiple gifts at the same coordinate.

Sample Input 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

Sample Output 3

7

Problem Statement

There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.

For each j=1,2,\ldots,Q, answer the following question.

• How many of the N students have a height of at least x_j?

Constraints

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

Sample Input 1

3 1
100 160 130
120

Sample Output 1

2

The students with a height of at least 120 are the 2-nd and 3-rd ones.

Sample Input 2

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

Sample Output 2

0
1
2
3
4

Sample Input 3

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

Sample Output 3

5
3
5
5
5

Problem Statement

There is a grid with N rows and N columns, where N is an odd number at most 45.

Let (i,j) denote the cell at the i-th row from the top and j-th column from the left.

In this grid, you will place Takahashi and a dragon consisting of N^2-1 parts numbered 1 to N^2-1 in such a way that satisfies the following conditions:

• Takahashi must be placed at the center of the grid, that is, in cell (\frac{N+1}{2},\frac{N+1}{2}).
• Except for the cell where Takahashi is, exactly one dragon part must be placed in each cell.
• For every integer x satisfying 2 \leq x \leq N^2-1, the dragon part x must be placed in a cell adjacent by an edge to the cell containing part x-1.
  • Cells (i,j) and (k,l) are said to be adjacent by an edge if and only if |i-k|+|j-l|=1.

Print one way to arrange the parts to satisfy the conditions. It is guaranteed that there is at least one arrangement that satisfies the conditions.

Constraints

• 3 \leq N \leq 45
• N is odd.

Sample Input 1

5

Sample Output 1

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

The following output also satisfies all the conditions and is correct.

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

On the other hand, the following outputs are incorrect for the reasons given.

Takahashi is not at the center.

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

The cells containing parts 23 and 24 are not adjacent by an edge.

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

Problem Statement

You have a grid with H rows from top to bottom and W columns from left to right. We denote by (i, j) the square at the i-th row from the top and j-th column from the left. (i,j)\ (1\leq i\leq H,1\leq j\leq W) has an integer A _ {i,j} between 1 and N written on it.

You are given integers h and w. For all pairs (k,l) such that 0\leq k\leq H-h and 0\leq l\leq W-w, solve the following problem:

• If you black out the squares (i,j) such that k\lt i\leq k+h and l\lt j\leq l+w, how many distinct integers are written on the squares that are not blacked out?

Note, however, that you do not actually black out the squares (that is, the problems are independent).

Constraints

• 1 \leq H,W,N \leq 300
• 1 \leq h \leq H
• 1 \leq w \leq W
• (h,w)\neq(H,W)
• 1 \leq A _ {i,j} \leq N\ (1\leq i\leq H,1\leq j\leq W)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

4 4 3
5 3 4

The given grid is as follows:

For example, when (k,l)=(0,0), four distinct integers 1,3,4, and 5 are written on the squares that are not blacked out, so 4 is the answer.

Sample Input 2

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

Sample Output 2

8 8 7
8 9 7
8 9 8

Sample Input 3

9 12 30 4 7
2 2 2 2 2 2 2 2 2 2 2 2
2 2 20 20 2 2 5 9 10 9 9 23
2 29 29 29 29 29 28 28 26 26 26 15
2 29 29 29 29 29 25 25 26 26 26 15
2 29 29 29 29 29 25 25 8 25 15 15
2 18 18 18 18 1 27 27 25 25 16 16
2 19 22 1 1 1 7 3 7 7 7 7
2 19 22 22 6 6 21 21 21 7 7 7
2 19 22 22 22 22 21 21 21 24 24 24

Sample Output 3

21 20 19 20 18 17
20 19 18 19 17 15
21 19 20 19 18 16
21 19 19 18 19 18
20 18 18 18 19 18
18 16 17 18 19 17

Problem Statement

You are given a tree with N vertices. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq N - 1) edge connects Vertices A_i and B_i.

We define the distance between Vertices u and v on this tree by the number of edges in the shortest path from Vertex u to Vertex v.

You are given Q queries. In the i-th (1 \leq i \leq Q) query, given integers U_i and K_i, print the index of any vertex whose distance from Vertex U_i is exactly K_i. If there is no such vertex, print -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq N - 1)
• The given graph is a tree.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq U_i, K_i \leq N \, (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4
1
-1

• Two vertices, Vertices 4 and 5, have a distance exactly 2 from Vertex 2.
• Only Vertex 1 has a distance exactly 3 from Vertex 5.
• No vertex has a distance exactly 3 from Vertex 3.

Sample Input 2

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

Sample Output 2

2
4
10
-1
-1