Problem Statement

You are given an integer N between 0 and 9999 (inclusive).

Print it as a four-digit string after appending to it the necessary number of leading zeros.

Constraints

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

Sample Input 1

321

Sample Output 1

0321

321 has three digits, so we need to add one leading zero to it to make it have four digits.

Sample Input 2

7777

Sample Output 2

7777

Sample Input 3

1

Sample Output 3

0001

Problem Statement

You are given N pairs of integers: (A_1, B_1), (A_2, B_2), \ldots, (A_N, B_N). For each i = 1, 2, \ldots, N, print A_i + B_i.

Constraints

• 1 \leq N \leq 1000
• -10^9 \leq A_i, B_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4
3 5
2 -6
-5 0
314159265 123456789

Sample Output 1

8
-4
-5
437616054

• The first line should contain A_1 + B_1 = 3 + 5 = 8.
• The second line should contain A_2 + B_2 = 2 + (-6) = -4.
• The third line should contain A_3 + B_3 = (-5) + 0 = -5.
• The fourth line should contain A_4 + B_4 = 314159265 + 123456789 = 437616054.

Problem Statement

On the xy-plane, there are N points with ID numbers from 1 to N. Point i is located at coordinates (X_i, Y_i), and no two points have the same coordinates.

From each point, find the farthest point and print its ID number. If multiple points are the farthest, print the smallest of the ID numbers of those points.

Here, we use the Euclidean distance: for two points (x_1,y_1) and (x_2,y_2), the distance between them is \sqrt{(x_1-x_2)^{2}+(y_1-y_2)^{2}}.

Constraints

• 2 \leq N \leq 100
• -1000 \leq X_i, Y_i \leq 1000
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All input values are integers.

Sample Input 1

4
0 0
2 4
5 0
3 4

Sample Output 1

3
3
1
1

The following figure shows the arrangement of the points. Here, P_i represents point i. The farthest point from point 1 are points 3 and 4, and point 3 has the smaller ID number.

The farthest point from point 2 is point 3.

The farthest point from point 3 are points 1 and 2, and point 1 has the smaller ID number.

The farthest point from point 4 is point 1.

Sample Input 2

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

Sample Output 2

6
6
6
6
6
4

Problem Statement

Print the color of the cell at the R-th row from the top and C-th column from the left in the following grid with 15 vertical rows and 15 horizontal columns.

Constraints

• 1 \leq R, C \leq 15
• R and C are integers.

Sample Input 1

3 5

Sample Output 1

black

In the grid above, the cell at the 3-rd row from the top and 5-th column from the left is black. Thus, black should be printed.

Sample Input 2

4 5

Sample Output 2

white

In the grid above, the cell at the 4-th row from the top and 5-th column from the left is white. Thus, white should be printed.

Problem Statement

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

• 1\leq D \leq 2\times 10^{12}
• All input values are integers.

Sample Input 1

21

Sample Output 1

1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

0

Sample Input 3

264428617

Sample Output 3

32

Problem Statement

We have a multiset of integers S, which is initially empty.

Given Q queries, process them in order. Each query is of one of the following types.

• 1 x: Insert an x into S.

• 2 x c: Remove an x from S m times, where m = \mathrm{min}(c,( the number of x's contained in S)).

• 3 : Print ( maximum value of S)-( minimum value of S). It is guaranteed that S is not empty when this query is given.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq Q
• When a query of type 3 is given, S is not empty.
• All values in input are integers.

Sample Input 1

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

Sample Output 1

1
5
4

The multiset S transitions as follows.

• 1-st query: insert 3 into S. S is now \lbrace 3 \rbrace.
• 2-nd query: insert 2 into S. S is now \lbrace 2, 3 \rbrace.
• 3-rd query: the maximum value of S = \lbrace 2, 3\rbrace is 3 and its minimum value is 2, so print 3-2=1.
• 4-th query: insert 2 into S. S is now \lbrace 2,2,3 \rbrace.
• 5-th query: insert 7 into S. S is now \lbrace 2, 2,3, 7\rbrace.
• 6-th query: the maximum value of S = \lbrace 2,2,3, 7\rbrace is 7 and its minimum value is 2, so print 7-2=5.
• 7-th query: since there are two 2's in S and \mathrm{min(2,3)} = 2, remove 2 from S twice. S is now \lbrace 3, 7\rbrace.
• 8-th query: the maximum value of S = \lbrace 3, 7\rbrace is 7 and its minimum value is 3, so print 7-3=4.

Sample Input 2

4
1 10000
1 1000
2 100 3
1 10

Sample Output 2

If the given queries do not contain that of type 3, nothing should be printed.

Problem Statement

You are given a positive integer N. It is known that N can be represented as N=p^2q using two different prime numbers p and q.

Find p and q.

You have T test cases to solve.

Constraints

• All values in the input are integers.
• 1\leq T\leq 10
• 1\leq N \leq 9\times 10^{18}
• N can be represented as N=p^2q using two different prime numbers p and q.

Sample Input 1

3
2023
63
1059872604593911

Sample Output 1

17 7
3 7
104149 97711

For the first test case, we have N=2023=17^2\times 7. Thus, p=17 and q=7.

Problem Statement

There is a town divided into a grid of cells with H rows and W columns. The cell at the i-th row from the top and j-th column from the left is a passable space if S_{i,j} is . and a block if S_{i,j} is #.

Takahashi will go from his house to a fish market. His house is in the cell at the top-left corner, and the fish market is in the cell at the bottom-right corner.

Takahashi can move one cell up, down, left, or right to a passable cell. He cannot leave the town. He cannot enter a block, either. However, his physical strength allows him to destroy all blocks in a square region with 2\times 2 cells of his choice with one punch, making these cells passable.

Find the minimum number of punches needed for Takahashi to reach the fish market.

Constraints

• 2 \leq H,W \leq 500
• H and W are integers.
• S_{i,j} is . or #.
• S_{1,1} and S_{H,W} are ..

Sample Input 1

5 5
..#..
#.#.#
##.##
#.#.#
..#..

Sample Output 1

1

He can reach the fish market by, for example, destroying the blocks in the square region with 2\times 2 cells marked * below.

..#..
#.**#
##**#
#.#.#
..#..

It is not required that all of the 2\times 2 cells in the region to punch are blocks.

Sample Input 2

5 7
.......
######.
.......
.######
.......

Sample Output 2

0

He can reach the fish market without destroying blocks, though he has to go a long way around.

Sample Input 3

8 8
.#######
########
########
########
########
########
########
#######.

Sample Output 3

5

Problem Statement

Given are M digits C_i.

Find the sum, modulo 998244353, of all integers between 1 and N (inclusive) that contain all of C_1, \ldots, C_M when written in base 10 without unnecessary leading zeros.

Constraints

• 1 \leq N < 10^{10^4}
• 1 \leq M \leq 10
• 0 \leq C_1 < \ldots < C_M \leq 9
• All values in input are integers.

Sample Input 1

104
2
0 1

Sample Output 1

520

Between 1 and 104, there are six integers that contain both 0 and 1 when written in base 10: 10,100,101,102,103,104.
The sum of them is 520.

Sample Input 2

999
4
1 2 3 4

Sample Output 2

0

Between 1 and 999, no integer contains all of 1, 2, 3, 4.

Sample Input 3

1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
5
0 2 4 6 8

Sample Output 3

397365274

Be sure to find the sum modulo 998244353.