Problem Statement

You are given a 6-digit positive integer N.
Determine whether N satisfies all of the following conditions.

• Among the digits of N, the digit 1 appears exactly once.
• Among the digits of N, the digit 2 appears exactly twice.
• Among the digits of N, the digit 3 appears exactly three times.

Constraints

• N is an integer satisfying 100000 \le N \le 999999.

Sample Input 1

123233

Sample Output 1

Yes

123233 satisfies the conditions in the problem statement, so print Yes.

Sample Input 2

123234

Sample Output 2

No

123234 does not satisfy the conditions in the problem statement, so print No.

Sample Input 3

323132

Sample Output 3

Yes

Sample Input 4

500000

Sample Output 4

No

Problem Statement

Iroha has a sequence of positive integers A = (A_1, A_2, \dots, A_N) of length N (N \ge 1).
She generated a string S using A as follows:

• Start with S = |.
• For i = 1, 2, \dots, N, perform the following operations in order:
  • Append A_i copies of - to the end of S.
  • Then, append one | to the end of S.

Given the generated string S, reconstruct the sequence A.

Constraints

• S is a string of length between 3 and 100, inclusive, generated by the method in the problem statement.
• A is a sequence of positive integers of length at least 1.

Sample Input 1

|---|-|----|-|-----|

Sample Output 1

3 1 4 1 5

S = |---|-|----|-|-----| is generated by A = (3, 1, 4, 1, 5).

Sample Input 2

|----------|

Sample Output 2

10

Sample Input 3

|-|-|-|------|

Sample Output 3

1 1 1 6

Problem Statement

You are given a string S of length N consisting of 0 and 1.
Move the K-th 1-block from the beginning in S to immediately after the (K-1)-th 1-block, and print the resulting string.

It is guaranteed that S contains at least K 1-blocks.

Here is a more precise description.

• Let S_{l\ldots r} denote the substring of S from the l-th character through the r-th character.
• We define a substring S_{l\ldots r} of S to be a 1-block if it satisfies all of the following conditions:
  • S_l = S_{l+1} = \cdots = S_r = 1
  • l = 1 or S_{l-1} = 0
  • r = N or S_{r+1} = 0

• Suppose that all 1-blocks in S are S_{l_1\ldots r_1}, \ldots, S_{l_m\ldots r_m}, where l_1 < l_2 < \cdots < l_m.

  Then, we define the length N string T, obtained by moving the K-th 1-block to immediately after the (K-1)-th 1-block, as follows:

  • T_i = S_i for 1 \leq i \leq r_{K-1}
  • T_i = 1 for r_{K-1} + 1 \leq i \leq r_{K-1} + (r_K - l_K) + 1
  • T_i = 0 for r_{K-1} + (r_K - l_K) + 2 \leq i \leq r_K
  • T_i = S_i for r_K + 1 \leq i \leq N

Constraints

• 1 \leq N \leq 5 \times 10^5
• S is a string of length N consisting of 0 and 1.
• 2 \leq K
• S contains at least K 1-blocks.

Sample Input 1

15 3
010011100011001

Sample Output 1

010011111000001

S has four 1-blocks: from the 2nd to the 2nd character, from the 5th to the 7th character, from the 11th to the 12th character, and from the 15th to the 15th character.

Sample Input 2

10 2
1011111111

Sample Output 2

1111111110

Problem Statement

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

We perform the following operation on S 10^{100} times:

• First, create a string T by changing uppercase letters in S to lowercase, and lowercase letters to uppercase.
• Then, concatenate S and T in this order to form a new S.

Answer Q queries. The i-th query is as follows:

• Find the K_i-th character from the beginning of S after all operations are completed.

Constraints

• S is a string consisting of uppercase and lowercase English letters, with length between 1 and 2 \times 10^5, inclusive.
• Q and K_i are integers.
• 1 \le Q \le 2 \times 10^5
• 1 \le K_i \le 10^{18}

Sample Input 1

aB
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Sample Output 1

a B A b A b a B A b a B a B A b

Before the operations, S = aB.

• After performing the operation once on aB, it becomes aBAb.
• After performing the operation twice on aB, it becomes aBAbAbaB.
• \dots

After performing the operation 10^{100} times, S = aBAbAbaBAbaBaBAb...

Sample Input 2

qWeRtYuIoP
8
1 1 2 3 5 8 13 21

Sample Output 2

q q W e t I E Q

Sample Input 3

AnUoHrjhgfLMcDIpzxXmEWPwBZvbKqQuiJTtFSlkNGVReOYCdsay
5
1000000000000000000 123456789 1 987654321 999999999999999999

Sample Output 3

K a A Z L

Problem Statement

There are N cells in a row, numbered 1 to N.
For each 1 \leq i < N, cells i and i+1 are adjacent.

Initially, cell i is painted with color i.

You are given Q queries. Process them in order. Each query is of one of the following two types.

• 1 x c: Repaint the following to color c: all reachable cells reachable from cell x by repeatedly moving to an adjacent cell painted in the same color as the current cell.
• 2 c: Print the number of cells painted with color c.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• In queries of the first type, 1 \leq x \leq N.
• In queries of the first and second types, 1 \leq c \leq N.
• There is at least one query of the second type.
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
4

The queries recolor the cells as shown in the figure.

Problem Statement

Takahashi and Aoki will play a game using cards with numbers written on them.

Initially, Takahashi has N cards with numbers A_1, \ldots, A_N in his hand, Aoki has M cards with numbers B_1, \ldots, B_M in his hand, and there are L cards with numbers C_1, \ldots, C_L on the table.
Throughout the game, both Takahashi and Aoki know all the numbers on all the cards, including the opponent's hand.

Starting with Takahashi, they take turns performing the following action:

• Choose one card from his hand and put it on the table. Then, if there is a card on the table with a number less than the number on the card he just played, he may take one such card from the table into his hand.

The player who cannot make a move first loses, and the other player wins. Determine who wins if both players play optimally.

It can be proved that the game always ends in a finite number of moves.

Constraints

• 1 \leq N, M, L
• N + M + L \leq 12
• 1 \leq A_i, B_i, C_i \leq 10^9
• All input values are integers.

Sample Input 1

1 1 2
2
4
1 3

Sample Output 1

Aoki

The game may proceed as follows (not necessarily optimal moves):

• Takahashi plays 2 from his hand to the table, and takes 1 from the table into his hand. Now, Takahashi's hand is (1), Aoki's hand is (4), and the table cards are (2,3).
• Aoki plays 4 from his hand to the table, and takes 2 into his hand. Now, Takahashi's hand is (1), Aoki's hand is (2), and the table cards are (3,4).
• Takahashi plays 1 from his hand to the table. Now, Takahashi's hand is (), Aoki's hand is (2), and the table cards are (1,3,4).
• Aoki plays 2 from his hand to the table. Now, Takahashi's hand is (), Aoki's hand is (), and the table cards are (1,2,3,4).
• Takahashi cannot make a move and loses; Aoki wins.

Sample Input 2

4 4 4
98 98765 987654 987654321
987 9876 9876543 98765432
123 12345 1234567 123456789

Sample Output 2

Takahashi

Sample Input 3

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

Sample Output 3

Aoki

Problem Statement

You are given a permutation P of (1,2,\dots,N) and an integer K.

Find the expected value, modulo 998244353, of the inversion number of P after performing the following operation:

• First, choose an integer i uniformly at random between 1 and N - K + 1, inclusive.
• Then, shuffle P_i, P_{i+1}, \dots, P_{i+K-1} uniformly at random.

Constraints

• All input values are integers.
• 1 \le K \le N \le 2 \times 10^5
• P is a permutation of (1,2,\dots,N).

Sample Input 1

4 2
1 4 2 3

Sample Output 1

166374061

The operation changes the permutation P into the following:

• (1,4,2,3) ... probability 1/2
• (4,1,2,3) ... probability 1/6
• (1,2,4,3) ... probability 1/6
• (1,4,3,2) ... probability 1/6

The expected value of the inversion number is \displaystyle 2 \times \frac{1}{2} + 3 \times \frac{1}{6} + 1 \times \frac{1}{6} + 3 \times \frac{1}{6} = \frac{13}{6}.

\displaystyle \frac{13}{6} modulo 998244353 is 166374061, so print this number.

Sample Input 2

1 1
1

Sample Output 2

0

Sample Input 3

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

Sample Output 3

499122200