Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.
You perform the following operation exactly K times:

• remove the initial element of A and append a 0 to the tail of A.

Print all the elements of A after the operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 100
• 1 \leq A_i \leq 100
• All values in the input are integers.

Sample Input 1

3 2
2 7 8

Sample Output 1

8 0 0

Before the operations, A = (2, 7, 8).
After performing the operation once, A = (7, 8, 0).
After performing the operation twice, A = (8, 0, 0).
Thus, (8, 0, 0) is the answer.

Sample Input 2

3 4
9 9 9

Sample Output 2

0 0 0

Sample Input 3

9 5
1 2 3 4 5 6 7 8 9

Sample Output 3

6 7 8 9 0 0 0 0 0

Problem Statement

Takahashi bought a table clock.
The clock shows the time as shown in Figure 1 at \mathrm{AB}:\mathrm{CD} in the 24-hour system.
For example, the clock in Figure 2 shows 7:58.

The format of the time is formally described as follows.
Suppose that the current time is m minutes past h in the 24-hour system. Here, the 24-hour system represents the hour by an integer between 0 and 23 (inclusive), and the minute by an integer between 0 and 59 (inclusive).
Let A be the tens digit of h, B be the ones digit of h, C be the tens digit of m, and D be the ones digit of m. (Here, if h has only one digit, we consider that it has a leading zero; the same applies to m.)
Then, the clock shows A in its top-left, B in its bottom-left, C in its top-right, and D in its bottom-right.

Takahashi has decided to call a time a confusing time if it satisfies the following condition:

• after swapping the top-right and bottom-left digits on the clock, it still reads a valid time in the 24-hour system.

For example, the clock in Figure 3 shows 20:13. After swapping its top-right and bottom-left digits, it reads 21:03. Thus, 20:13 is a confusing time.

The clock now shows H:M.
Find the next confusing time (including now) in the 24-hour system.

Constraints

• 0 \leq H \leq 23
• 0 \leq M \leq 59
• H and M are integers.

Sample Input 1

1 23

Sample Output 1

1 23

1:23 is a confusing time because, after swapping its top-right and bottom-left digits on the clock, it reads 2:13.
Thus, the answer is 1:23.
Your answer is considered correct even if you print 01 23 with a leading zero.

Sample Input 2

19 57

Sample Output 2

20 0

The next confusing time after 19:57 is 20:00.

Sample Input 3

20 40

Sample Output 3

21 0

Note that 24:00 is an invalid notation in the 24-hour system.

Problem Statement

Takahashi runs an SNS "Twidai," which has N users from user 1 through user N. In Twidai, users can follow or unfollow other users.

Q operations have been performed since Twidai was launched. The i-th (1\leq i\leq Q) operation is represented by three integers T_i, A_i, and B_i, whose meanings are as follows:

• If T_i = 1: it means that user A_i follows user B_i. If user A_i is already following user B_i at the time of this operation, it does not make any change.
• If T_i = 2: it means that user A_i unfollows user B_i. If user A_i is not following user B_i at the time of this operation, it does not make any change.
• If T_i = 3: it means that you are asked to determine if users A_i and B_i are following each other. You need to print Yes if user A_i is following user B_i and user B_i is following user A_i, and No otherwise.

When the service was launched, no users were following any users.

Print the correct answers for all operations such that T_i = 3 in ascending order of i.

Constraints

• 2 \leq N \leq 10 ^ 9
• 1 \leq Q \leq 2\times10 ^ 5
• T _ i=1,2,3\ (1\leq i\leq Q)
• 1 \leq A _ i \leq N\ (1\leq i\leq Q)
• 1 \leq B _ i \leq N\ (1\leq i\leq Q)
• A _ i\neq B _ i\ (1\leq i\leq Q)
• There exists i\ (1\leq i\leq Q) such that T _ i=3.
• All values in the input are integers.

Sample Input 1

3 9
1 1 2
3 1 2
1 2 1
3 1 2
1 2 3
1 3 2
3 1 3
2 1 2
3 1 2

Sample Output 1

No
Yes
No
No

Twidai has three users. The nine operations are as follows.

• User 1 follows user 2. No other users are following or followed by any users.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, but user 2 is not following user 1, so No is the correct answer to this operation.
• User 2 follows user 1.
• Determine if users 1 and 2 are following each other. User 1 is following user 2, and user 2 is following user 1, so Yes is the correct answer to this operation.
• User 2 follows user 3.
• User 3 follows user 2.
• Determine if users 1 and 3 are following each other. User 1 is not following user 3, and user 3 is not following user 1, so No is the correct answer to this operation.
• User 1 unfollows user 2.
• Determine if users 1 and 2 are following each other. User 2 is following user 1, but user 1 is not following user 2, so No is the correct answer to this operation.

Sample Input 2

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

Sample Output 2

Yes
No

A user may follow the same user multiple times.

Sample Input 3

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

Sample Output 3

No
No
No
No
Yes
Yes
No
No
No
Yes
Yes

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.

Given Q queries, process all of them in order. The q-th (1\leq q\leq Q) query is in one of the following three formats, which represents the following queries:

• 1\ x _ q: assign x_q to every element of A.
• 2\ i _ q\ x _ q: add x_q to A _ {i _ q}.
• 3\ i _ q: print the value of A _ {i _ q}.

Constraints

• 1 \leq N \leq 2\times10^5
• 1 \leq Q \leq 2\times10^5
• 0 \leq A _ i \leq 10^9\ (1\leq i\leq N)
• If the q-th (1\leq q\leq Q) query is in the second or third format, 1 \leq i _ q \leq N.
• If the q-th (1\leq q\leq Q) query is in the first or second format, 0 \leq x _ q \leq 10^9.
• There exists a query in the third format.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1
8
5

Initially, A=(3,1,4,1,5). The queries are processed as follows:

• A_2=1, so print 1.
• Add 4 to A_3, making A=(3,1,8,1,5).
• A_3=8, so print 8.
• Assign 1 to every element of A, making A=(1,1,1,1,1).
• Add 4 to A_3, making A=(1,1,5,1,1).
• A_3=5, so print 5.

Sample Input 2

1
1000000000
8
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
3 1

Sample Output 2

8000000000

Note that the elements of A may not fit into a 32-bit integer type.

Sample Input 3

10
1 8 4 15 7 5 7 5 8 0
20
2 7 0
3 7
3 8
1 7
3 3
2 4 4
2 4 9
2 10 5
1 10
2 4 2
1 10
2 3 1
2 8 11
2 3 14
2 1 9
3 8
3 8
3 1
2 6 5
3 7

Sample Output 3

7
5
7
21
21
19
10

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 N strings S _ 1,S _ 2,\ldots,S _ N. S _ i\ (1\leq i\leq N) is a non-empty string of length at most 10 consisting of lowercase English letters, and the strings are pairwise distinct.

Taro the First and Jiro the Second play a word-chain game. In this game, the two players take alternating turns, with Taro the First going first. In each player's turn, the player chooses an integer i\ (1\leq i\leq N), which should satisfy the following two conditions:

• i is different from any integer chosen by the two players so far since the game started;
• the current turn is the first turn of the game, or the last character of S_j equals the first character of S_i, where j is the last integer chosen.

The player who is unable to choose a conforming i loses; the other player wins.

Determine which player will win if the two players play optimally.

Constraints

• 1 \leq N \leq 16
• N is an integer.
• S _ i\ (1\leq i\leq N) is a non-empty string of length at most 10 consisting of lowercase English letters.
• S _ i\neq S _ j\ (1\leq i\lt j\leq N)

Sample Input 1

6
enum
float
if
modint
takahashi
template

Sample Output 1

First

For example, the game progresses as follows. Note that the two players may not be playing optimally in this example.

• Taro the First chooses i=3. S _ i=if.
• Jiro the Second chooses i=2. S _ i=float, and the last character of if equals the first character of float.
• Taro the First chooses i=5. S _ i=takahashi, and the last character of float equals the first character of takahashi.
• Jiro the Second is unable to choose i\neq2,3,5 such that S _ i starts with i, so he loses.

In this case, Taro the First wins.

Sample Input 2

10
catch
chokudai
class
continue
copy
exec
havoc
intrinsic
static
yucatec

Sample Output 2

Second

Sample Input 3

16
mnofcmzsdx
lgeowlxuqm
ouimgdjxlo
jhwttcycwl
jbcuioqbsj
mdjfikdwix
jhvdpuxfil
peekycgxco
sbvxszools
xuuqebcrzp
jsciwvdqzl
obblxzjhco
ptobhnpfpo
muizaqtpgx
jtgjnbtzcl
sivwidaszs

Sample Output 3

First

Problem Statement

This is an interactive task (where your program interacts with the judge's program via Standard Input and Output).

You are given integers N, L, and R.
You play the following game against the judge:

There are N cards numbered 1 through N on the table.
The players alternately perform the following operation:

• choose an integer pair (x, y) satisfying 1 \leq x \leq N, L \leq y \leq R such that all of the y cards x, x+1, \dots, x+y-1 remain on the table, and remove cards x, x+1, \dots, x+y-1 from the table.

The first player to become unable to perform the operation loses, and the other player wins.

Choose whether to go first or second, and play the game against the judge to win.

Constraints

• 1 \leq N \leq 2000
• 1 \leq L \leq R \leq N
• N, L, and R are integers.

Input and Output

This is an interactive task (where your program interacts with the judge's program via Standard Input and Output).

Initially, receive N, L, and R, given from the input in the following format:

N L R

First, you choose whether to go first or second. Print First if you choose to go first, and Second if you choose to go second.

Then, the game immediately starts. If you choose to go first, the judge goes second, and vice versa. You are to interact with the judge via input and output until the game ends to win the game.

In your turn, print an integer pair (x, y) that you choose in the operation in the following format. If there is no (x, y) that you can choose, print (x, y) = (0, 0) instead.

x y

In the judge's turn, the judge print an integer pair (a, b) in the following format:

a b

Here, it is guaranteed that (a, b) is of one of the following three kinds.

• If (a, b) = (0, 0): the judge is unable to perform the operation. In other words, you have won the game.
• If (a, b) = (-1, -1): you have chosen an illegal (x, y) or printed (0, 0). In other words, you have lost the game.
• Otherwise: the judge has performed the operation with (x,y) = (a,b). It is guaranteed that judge chooses valid (x, y).

If the judge returns (a,b)=(0,0) or (a,b)=(-1,-1), the game has already ended. In that case, terminate the program immediately.

Notes

• After each output, add a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.
• If an invalid output is printed during the interaction, or if the program terminates halfway, the verdict will be indeterminate. Especially, note that if a runtime error occurs during the execution of the program, you may get a WA or TLE verdict instead of a RE verdict.
• Terminate the program immediately after the game ends. Otherwise, the verdict will be indeterminate.

Sample Interaction

The following is a sample interaction where N = 6, L = 1, and R = 2.

Problem Statement

A sequence S of non-negative integers is said to be a good sequence if:

• there exists a non-empty (not necessarily contiguous) subsequence T of S such that the bitwise XOR of all elements in T is 1.

There are an empty sequence A, and 2^B cards with each of the integers between 0 and 2^B-1 written on them.
You repeat the following operation until A becomes a good sequence:

• You freely choose a card and append the integer written on it to the tail of A. Then, you eat the card. (Once eaten, the card cannot be chosen anymore.)

How many sequences of length N can be the final A after the operations? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq B \leq 10^7
• N \leq 2^B
• N and B are integers.

Sample Input 1

2 2

Sample Output 1

5

The following five sequences of length 2 can be the final A after the operations.

• (0, 1)
• (2, 1)
• (2, 3)
• (3, 1)
• (3, 2)

Sample Input 2

2022 1119

Sample Output 2

293184537

Sample Input 3

200000 10000000

Sample Output 3

383948354