Problem Statement

You are given an integer Y between 1583 and 2023.

Find the number of days in the year Y of the Gregorian calendar.

Within the given range, the year Y has the following number of days:

• if Y is not a multiple of 4, then 365 days;

• if Y is a multiple of 4 but not a multiple of 100, then 366 days;

• if Y is a multiple of 100 but not a multiple of 400, then 365 days;

• if Y is a multiple of 400, then 366 days.

Constraints

• Y is an integer between 1583 and 2023, inclusive.

Sample Input 1

2023

Sample Output 1

365

2023 is not a multiple of 4, so it has 365 days.

Sample Input 2

1992

Sample Output 2

366

1992 is a multiple of 4 but not a multiple of 100, so it has 366 days.

Sample Input 3

1800

Sample Output 3

365

1800 is a multiple of 100 but not a multiple of 400, so it has 365 days.

Sample Input 4

1600

Sample Output 4

366

1600 is a multiple of 400, so it has 366 days.

Problem Statement

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

Swap the a-th and b-th characters from the beginning of S and print the resulting string.

Constraints

• S is a string consisting of lowercase English letters.
• The length of S, |S|, satisfies 2 \leq |S| \leq 10.
• 1 \leq a < b \leq |S|
• a and b are integers.

Sample Input 1

chokudai
3 5

Sample Output 1

chukodai

After swapping the 3-rd character o and 5-th character u of chokudai, we have chukodai.

Sample Input 2

aa
1 2

Sample Output 2

aa

In this sample, after swapping the 1-st and 2-nd characters of S, we have the same string as S.

Sample Input 3

aaaabbbb
1 8

Sample Output 3

baaabbba

Problem Statement

Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.

• Round X off to the nearest 10^i.
  • Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
  • Here are some examples:
    • Rounding 273 off to the nearest 10^2 yields 300.
    • Rounding 999 off to the nearest 10^3 yields 1000.
    • Rounding 100 off to the nearest 10^{10} yields 0.
    • Rounding 1015 off to the nearest 10^1 yields 1020.

Constraints

• X and K are integers.
• 0 \le X < 10^{15}
• 1 \le K \le 15

Sample Input 1

2048 2

Sample Output 1

2100

X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.

Sample Input 2

1 15

Sample Output 2

0

Sample Input 3

999 3

Sample Output 3

1000

Sample Input 4

314159265358979 12

Sample Output 4

314000000000000

X may not fit into a 32-bit integer type.

Problem Statement

You are given integers A and B, in base K.
Print A \times B in decimal.

Notes

For base-K representation, see Wikipedia's article on Positional notation.

Constraints

• 2 \leq K \leq 10
• 1 \leq A,B \leq 10^5
• A and B are in base-K representation.

Sample Input 1

2
1011 10100

Sample Output 1

220

1011 in base 2 corresponds to 11 in base 10.
10100 in base 2 corresponds to 20 in base 10.
We have 11 \times 20 = 220, so print 220.

Sample Input 2

7
123 456

Sample Output 2

15642

123 in base 7 corresponds to 66 in base 10.
456 in base 7 corresponds to 237 in base 10.
We have 66 \times 237 = 15642, so print 15642.

Problem Statement

We have N boxes numbered 1 to N that are initially empty, and an unlimited number of blank cards.
Process Q queries in order. There are three kinds of queries as follows.

• 1 i j \colon Write the number i on a blank card and put it into box j.
• 2 i \colon Report all numbers written on the cards in box i, in ascending order.
• 3 i \colon Report all box numbers of the boxes that contain a card with the number i, in ascending order.

Here, note the following.

• In a query of the second kind, if box i contains multiple cards with the same number, that number should be printed the number of times equal to the number of those cards.
• In a query of the third kind, even if a box contains multiple cards with the number i, the box number of that box should be printed only once.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• For a query of the first kind:
  • 1 \leq i \leq 2 \times 10^5
  • 1 \leq j \leq N
• For a query of the second kind:
  • 1 \leq i \leq N
  • Box i contains some cards when this query is given.
• For a query of the third kind:
  • 1 \leq i \leq 2 \times 10^5
  • Some boxes contain a card with the number i when this query is given.
• At most 2 \times 10^5 numbers are to be reported.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1 2
1 1 2
1 4
4

Let us process the queries in order.

• Write 1 on a card and put it into box 1.
• Write 2 on a card and put it into box 4.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1 and 2.
  • Print 1 and 2 in this order.
• Write 1 on a card and put it into box 4.
• Box 4 contains cards with the numbers 1, 1, and 2.
  • Note that you should print 1 twice.
• Boxes 1 and 4 contain a card with the number 1.
  • Note that you should print 4 only once, even though box 4 contains two cards with the number 1.
• Boxes 4 contains a card with the number 2.

Sample Input 2

1
5
1 1 1
1 2 1
1 200000 1
2 1
3 200000

Sample Output 2

1 2 200000
1

Problem Statement

You are given two sequences: A=(A_1,A_2, \ldots ,A_N) consisting of N positive integers, and B=(B_1, \ldots ,B_M) consisting of M positive integers.

Find the minimum difference of an element of A and an element of B, that is, \displaystyle \min_{ 1\leq i\leq N}\displaystyle\min_{1\leq j\leq M} \lvert A_i-B_j\rvert.

Constraints

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

Sample Input 1

2 2
1 6
4 9

Sample Output 1

2

Here is the difference for each of the four pair of an element of A and an element of B: \lvert 1-4\rvert=3, \lvert 1-9\rvert=8, \lvert 6-4\rvert=2, and \lvert 6-9\rvert=3. We should print the minimum of these values, or 2.

Sample Input 2

1 1
10
10

Sample Output 2

0

Sample Input 3

6 8
82 76 82 82 71 70
17 39 67 2 45 35 22 24

Sample Output 3

3

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i,j) the cell at the i-th row from the top and j-th column from the left. Each cell in the grid has a lowercase English letter written on it. The letter written on (i,j) equals the j-th character of a given string S_i.

Snuke will repeat moving to an adjacent cell sharing a side to travel from (1,1) to (H,W). Determine if there is a path in which the letters written on the visited cells (including initial (1,1) and final (H,W)) are s \rightarrow n \rightarrow u \rightarrow k \rightarrow e \rightarrow s \rightarrow n \rightarrow \dots, in the order of visiting. Here, a cell (i_1,j_1) is said to be an adjacent cell of (i_2,j_2) sharing a side if and only if |i_1-i_2|+|j_1-j_2| = 1.

Formally, determine if there is a sequence of cells ((i_1,j_1),(i_2,j_2),\dots,(i_k,j_k)) such that:

• (i_1,j_1) = (1,1),(i_k,j_k) = (H,W);
• (i_{t+1},j_{t+1}) is an adjacent cell of (i_t,j_t) sharing a side, for all t\ (1 \leq t < k); and
• the letter written on (i_t,j_t) coincides with the (((t-1) \bmod 5) + 1)-th character of snuke, for all t\ (1 \leq t \leq k).

Constraints

• 2\leq H,W \leq 500
• H and W are integers.
• S_i is a string of length W consisting of lowercase English letters.

Sample Input 1

2 3
sns
euk

Sample Output 1

Yes

The path (1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3) satisfies the conditions because they have s \rightarrow n \rightarrow u \rightarrow k written on them, in the order of visiting.

Sample Input 2

2 2
ab
cd

Sample Output 2

No

Sample Input 3

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

Sample Output 3

Yes

Problem Statement

This is an interactive problem (where your program interacts with the judge via input and output).

You are given a positive integer N and integers L and R such that 0 \leq L \leq R < 2^N. The judge has a hidden sequence A = (A_0, A_1, \dots, A_{2^N-1}) consisting of integers between 0 and 99, inclusive.

Your goal is to find the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100. However, you cannot directly know the values of the elements in the sequence A. Instead, you can ask the judge the following question:

• Choose non-negative integers i and j such that 2^i(j+1) \leq 2^N. Let l = 2^i j and r = 2^i (j+1) - 1. Ask for the remainder when A_l + A_{l+1} + \dots + A_r is divided by 100.

Let m be the minimum number of questions required to determine the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100 for any sequence A. You need to find this remainder within m questions.

Constraints

• 1 \leq N \leq 18
• 0 \leq L \leq R \leq 2^N - 1
• All input values are integers.

Input and Output

This is an interactive problem (where your program interacts with the judge via input and output).

First, read the integers N, L, and R from Standard Input:

N L R

Then, repeat asking questions until you can determine the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100. Each question should be printed in the following format:

? i j

Here, i and j must satisfy the following constraints:

• i and j are non-negative integers.
• 2^i(j+1) \leq 2^N

The response to the question will be given in the following format from Standard Input:

T

Here, T is the answer to the question, which is the remainder when A_l + A_{l+1} + \dots + A_r is divided by 100, where l = 2^i j and r = 2^i (j+1) - 1.

If i and j do not satisfy the constraints, or if the number of questions exceeds m, then T will be -1.

If the judge returns -1, your program is already considered incorrect. In this case, terminate the program immediately.

Once you have determined the remainder when A_L + A_{L+1} + \dots + A_R is divided by 100, print the remainder S in the following format and terminate the program immediately:

! S

Notes

• At the end of each output, print a newline and flush Standard Output. Otherwise, the verdict may be TLE.
• If your output is malformed or your program exits prematurely, the verdict will be indeterminate.
• After printing the answer, terminate the program immediately. Otherwise, the verdict will be indeterminate.

Example

Here is an example for N=3, L=1, R=5, and A=(31, 41, 59, 26, 53, 58, 97, 93). In this case, m=3, so you can ask up to three questions.

Problem Statement

There is a road extending east and west, and N persons are on the road. The road extends infinitely long to the east and west from a point called the origin.

The i-th person (1\leq i\leq N) is initially at a position X_i meters east from the origin.

The persons can move along the road to the east or west. Specifically, they can perform the following movement any number of times.

• Choose one person. If there is no other person at the destination, move the chosen person 1 meter east or west.

They have Q tasks in total, and the i-th task (1\leq i\leq Q) is as follows.

• The T_i-th person arrives at coordinate G_i.

Find the minimum total number of movements required to complete all Q tasks in order.

Constraints

• 1\leq N\leq2\times10^5
• 0\leq X_1 < X_2 < \dotsb < X_N \leq10^8
• 1\leq Q\leq2\times10^5
• 1\leq T_i\leq N\ (1\leq i\leq Q)
• 0\leq G_i\leq10^8\ (1\leq i\leq Q)
• All input values are integers.

Sample Input 1

5
10 20 30 40 50
4
3 45
4 20
1 35
2 60

Sample Output 1

239

An optimal sequence of movements for the persons is as follows (the positions of the persons are not necessarily drawn to scale):

For each task, the persons move as follows.

• The 4th person moves 6 steps east, and the 3rd person moves 15 steps east.
• The 2nd person moves 2 steps west, the 3rd person moves 26 steps west, and the 4th person moves 26 steps west.
• The 4th person moves 18 steps east, the 3rd person moves 18 steps east, the 2nd person moves 18 steps east, and the 1st person moves 25 steps east.
• The 5th person moves 13 steps east, the 4th person moves 24 steps east, the 3rd person moves 24 steps east, and the 2nd person moves 24 steps east.

The total number of movements is 21+54+79+85=239.

You cannot complete all tasks with a total movement count of 238 or less, so print 239.

Sample Input 2

8
0 1 2 3 4 5 6 100000000
6
1 100000000
8 0
1 100000000
8 4
1 100000000
5 21006578

Sample Output 2

4294967297

Note that some persons may need to move to the west of the origin or more than 10^8 meters to the east of it.

Also, note that the answer may exceed 2^{32}.

Sample Input 3

12
1558 3536 3755 3881 4042 4657 5062 7558 7721 8330 8542 9845
8
9 1694
7 3296
12 5299
5 5195
5 5871
1 2491
8 1149
8 2996

Sample Output 3

89644