Problem Statement

Below, a 01-sequence is a string consisting of 0 and 1.

You are given two 01-sequences S and T of length N each. Print the lexicographically smallest 01-sequence U of length N that satisfies the condition below.

• The Hamming distance between S and U equals the Hamming distance between T and U.

If there is no such 01-sequence U of length N, print -1 instead.

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• S and T are 01-sequences of length N each.

Sample Input 1

5
00100
10011

Sample Output 1

00001

For U = 00001, the Hamming distance between S and U and the Hamming distance between T and U are both 2. Additionally, this is the lexicographically smallest 01-sequence U of length N that satisfies the condition.

Sample Input 2

1
0
1

Sample Output 2

-1

No 01-sequence U of length N satisfies the condition, so -1 should be printed.

Problem Statement

You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N).

Print the number of integer sequences A = (A_1, A_2, \ldots, A_N) of length N that satisfy both of the conditions below, modulo 998244353.

• 1 \leq A_i \leq M for every i = 1, 2, \ldots, N.
• The integer sequence A is lexicographically smaller than the integer sequence (A_{P_1}, A_{P_2}, \ldots, A_{P_N}).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^9
• 1 \leq P_i \leq N
• i \neq j \implies P_i \neq P_j
• All values in the input are integers.

Sample Input 1

4 2
4 1 3 2

Sample Output 1

6

Six integer sequences A satisfy both of the conditions: (1, 1, 1, 2), (1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 2, 2), (2, 1, 1, 2), and (2, 1, 2, 2).
For instance, when A = (1, 1, 1, 2), we have (A_{P_1}, A_{P_2}, A_{P_3}, A_{P_4}) = (2, 1, 1, 1), which is lexicographically larger than A.

Sample Input 2

1 1
1

Sample Output 2

0

Sample Input 3

20 100000
11 15 3 20 17 6 1 9 5 19 10 16 7 8 12 2 18 14 4 13

Sample Output 3

55365742

Problem Statement

There are N squares called square 1, square 2, \ldots, square N, where square i and square i+1 are adjacent for each i = 1, 2, \ldots, N-1.

Initially, M of the squares have 0 or 1 written on them. Specifically, for each i = 1, 2, \ldots, M, Y_i is written on square X_i. The other N-M squares have nothing written on them.

Takahashi and Aoki will play a game against each other. The two will alternately act as follows, with Takahashi going first.

• Choose a square with nothing written yet, and write 0 or 1 on that square. Here, it is forbidden to make two adjacent squares have the same digit written on them.

The first player to be unable to act loses; the other player wins.

Determine the winner when both players adopt the optimal strategy for their own victory.

Constraints

• 1 \leq N \leq 10^{18}
• 0 \leq M \leq \min\lbrace N, 2 \times 10^5 \rbrace
• 1 \leq X_1 \lt X_2 \lt \cdots \lt X_M \leq N
• Y_i \in \lbrace 0, 1\rbrace
• X_i + 1 = X_{i+1} \implies Y_i \neq Y_{i+1}
• All values in the input are integers.

Sample Input 1

7 2
2 0
4 1

Sample Output 1

Takahashi

Here is one possible progression of the game.

1. Takahashi writes 0 on square 6.
2. Aoki writes 1 on square 1.
3. Takahashi writes 1 on square 7.

Then, Aoki cannot write 0 or 1 on any square, so Takahashi wins.

Sample Input 2

3 3
1 1
2 0
3 1

Sample Output 2

Aoki

Since every square already has 0 or 1 written at the beginning, Takahashi, who goes first, cannot act, so Aoki wins.

Sample Input 3

1000000000000000000 0

Sample Output 3

Aoki

Problem Statement

You are given an integer sequence A = (A_0, A_1, \ldots, A_{2^N-1}) of length 2^N.

Additionally, Q queries are given. For each i = 1, 2, \ldots, Q, the i-th query is represented by two integers X_i and Y_i and asks you to perform the operation below.

For each j = 0, 1, 2, \ldots, 2^N-1 in this order, do the following.

1. First, let b_{N-1}b_{N-2}\ldots b_0 be the binary representation of j with N digits. Additionally, let j' be the integer represented by the binary representation b_{N-1}b_{N-2}\ldots b_0 after flipping the bit b_{X_i} (changing 0 to 1 and 1 to 0).
2. Then, if b_{X_i} = Y_i, add the value of A_j to A_{j'}.

Print each element of A, modulo 998244353, after processing all the queries in the order they are given in the input.

Constraints

• 1 \leq N \leq 18
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A_i \lt 998244353
• 0 \leq X_i \leq N-1
• Y_i \in \lbrace 0, 1\rbrace
• All values in the input are integers.

Sample Input 1

2 2
0 1 2 3
1 1
0 0

Sample Output 1

2 6 2 5

The first query asks you to do the following.

• For j = 0, we have b_1b_0 = 00 and j' = 2. Since b_1 \neq 1, skip the addition.
• For j = 1, we have b_1b_0 = 01 and j' = 3. Since b_1 \neq 1, skip the addition.
• For j = 2, we have b_1b_0 = 10 and j' = 0. Since b_1 = 1, add the value of A_2 to A_0. Now we have A = (2, 1, 2, 3).
• For j = 3, we have b_1b_0 = 11 and j' = 1. Since b_1 = 1, add the value of A_3 to A_1. Now we have A = (2, 4, 2, 3).

The second query asks you to do the following.

• For j = 0, we have b_1b_0 = 00 and j' = 1. Since b_0 = 0, add the value of A_0 to A_1. Now we have A = (2, 6, 2, 3).
• For j = 1, we have b_1b_0 = 01 and j' = 0. Since b_0 \neq 0, skip the addition.
• For j = 2, we have b_1b_0 = 10 and j' = 3. Since b_0 = 0, add the value of A_2 to A_3. Now we have A = (2, 6, 2, 5).
• For j = 3, we have b_1b_0 = 11 and j' = 2. Since b_0 \neq 0, skip the addition.

Thus, A will be (2, 6, 2, 5) after processing all the queries.

Sample Input 2

3 10
606248357 338306877 919152167 981537317 808873985 845549408 680941783 921035119
1 1
0 0
0 0
0 0
0 1
0 1
0 1
2 0
2 0
2 0

Sample Output 2

246895115 904824001 157201385 744260759 973709546 964549010 61683812 205420980

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N) of length N. Additionally, its contiguous subsequences of lengths P and Q are given: X = (X_1, X_2, \ldots, X_P) and Y = (Y_1, Y_2, \ldots, Y_Q).

You can perform the four operations on X below any number of times (possibly zero) in any order.

• Add an arbitrary integer at the beginning of X.
• Delete the element at the beginning of X.
• Add an arbitrary integer at the end of X.
• Delete the element at the end of X.

Here, X must be a non-empty contiguous subsequence of A before and after each operation. Find the minimum total number of operations needed to make X equal Y. Under the Constraints of this problem, it is guaranteed that one can always make X equal Y by repeating operations.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• 1 \leq P, Q \leq N
• (X_1, X_2, \ldots, X_P) and (Y_1, Y_2, \ldots, Y_Q) are contiguous subsequences of (A_1, A_2, \ldots, A_N).
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

3

You can make X equal Y while keeping X a non-empty contiguous subsequence of A, as follows.

1. First, delete the element at the beginning of X. Now, you have X = (1).
2. Next, add 5 at the end of X. Now, you have X = (1, 5).
3. Furthermore, add 7 at the end of X. Now, you have X = (1, 5, 7), which equal Y.

Here, you perform three operations, which is the fewest possible.

Sample Input 2

20
2 5 1 2 7 7 4 5 3 7 7 4 5 5 5 4 6 5 6 1
6
1 2 7 7 4 5
7
7 4 5 5 5 4 6

Sample Output 2

7

Problem Statement

Takahashi and Aoki will play a game against each other using cards in three colors: red, green, and blue.

Initially, Takahashi has R_1 red, G_1 green, and B_1 blue cards, and Aoki has R_2 red, G_2 green, and B_2 blue cards in their hands. Each player knows the hands of both players. The game starts with Takahashi on offense and Aoki on defense, and repeats the process below.

1. First, the player on offense plays an arbitrary card from his hand.
2. Then, the player on defense either plays a card with the same color from his hand, or does nothing. If a card is played, the players switch between offense and defense.

The first player to have zero cards in his hand wins the game. Determine the winner when both players adopt the optimal strategy for their own victory.

For each input file, solve T independent test cases.

Constraints

• 1 \leq T \leq 10^5
• 0 \leq R_1, G_1, B_1, R_2, G_2, B_2 \leq 10^{18}
• R_1 + G_1 + B_1 \geq 1
• R_2 + G_2 + B_2 \geq 1
• All values in the input are integers.

Sample Input 1

10
1 1 1 0 1 2
1 2 3 4 5 6
1 2 3 3 2 1
1 0 1 0 1 0
1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000
711741968710511023 863182190136397525 935042422763027373 565732706644706921 453428280447672223 188382995979861200
166020598057882490 762504522442931582 957390622951053643 932567512152300679 473764934043971365 82803157126515469
895348321962139989 376963632541282296 624486091834022571 175064808312523035 217537722506696493 203742827664922704
802346905414720749 973713209304621356 275109783325269828 588060532191410837 516874290286751783 747001196732741840
539971830806602684 270896673960719346 124580938028911221 18175990488280605 360214649380675201 155957964634289774

Sample Output 1

Takahashi
Takahashi
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

For the first test case, here is one possible progression of the game.

1. Takahashi, who is on offense, plays a red card.
2. Aoki, who is on defense, responds by doing nothing. (Since he has no red cards, this is the only choice.)
3. Takahashi, who is on offense, plays a green card.
4. Aoki, who is on defense, responds by playing a green card. The players switch between offense and defense.
5. Aoki, who is on offense, plays a blue card.
6. Takahashi, who is on defense, responds by playing a blue card.
7. Takahashi is the first player to have zero cards in his hand, so he wins.