Problem Statement

There is a bottle of disinfectant that can disinfect exactly M hands.

N aliens come one by one to disinfect their hands.
The i-th alien (1 \leq i \leq N) has H_i hands and wants to disinfect all of their hands once.

Determine how many aliens can disinfect all of their hands.
Here, even if there is not enough disinfectant left for an alien to disinfect all of their hands when they start, they will use up the remaining disinfectant.

Constraints

• 1 \leq N, M \leq 100
• 1 \leq H_i \leq 100
• All input values are integers.

Sample Input 1

5 10
2 3 2 5 3

Sample Output 1

3

The aliens disinfect their hands in the following steps:

• The first alien disinfects their two hands. The remaining disinfectant can disinfect 10-2=8 hands.
• The second alien disinfects their three hands. The remaining disinfectant can disinfect 8-3=5 hands.
• The third alien disinfects their two hands. The remaining disinfectant can disinfect 5-2=3 hands.
• The fourth alien has five hands, but there is only enough disinfectant for three hands, so they use up the disinfectant without disinfecting all of their hands.

Thus, the first three aliens can disinfect all of their hands, so print 3.

Sample Input 2

5 10
2 3 2 3 5

Sample Output 2

4

Sample Input 3

1 5
1

Sample Output 3

1

All aliens can disinfect their hands.

Problem Statement

Given N, print 2^N.

Constraints

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

Sample Input 1

3

Sample Output 1

8

We have 2^3=8.

Sample Input 2

30

Sample Output 2

1073741824

Problem Statement

We define Extended A strings, Extended B strings, Extended C strings, and Extended ABC strings as follows:

• A string S is an Extended A string if all characters in S are A.
• A string S is an Extended B string if all characters in S are B.
• A string S is an Extended C string if all characters in S are C.
• A string S is an Extended ABC string if there is an Extended A string S_A, an Extended B string S_B, and an Extended C string S_C such that the string obtained by concatenating S_A, S_B, S_C in this order equals S.

For example, ABC, A, and AAABBBCCCCCCC are Extended ABC strings, but ABBAAAC and BBBCCCCCCCAAA are not. Note that the empty string is an Extended A string, an Extended B string, and an Extended C string.

You are given a string S consisting of A, B, and C. If S is an Extended ABC string, print Yes; otherwise, print No.

Constraints

• S is a string consisting of A, B, and C.
• 1\leq|S|\leq 100 (|S| is the length of the string S.)

Sample Input 1

AAABBBCCCCCCC

Sample Output 1

Yes

AAABBBCCCCCCC is an Extended ABC string because it is a concatenation of an Extended A string of length 3, AAA, an Extended B string of length 3, BBB, and an Extended C string of length 7, CCCCCCC, in this order.

Thus, print Yes.

Sample Input 2

ACABABCBC

Sample Output 2

No

There is no triple of Extended A string S_A, Extended B string S_B, and Extended C string S_C such that the string obtained by concatenating S_A, S_B, and S_C in this order equals ACABABCBC.

Therefore, print No.

Sample Input 3

A

Sample Output 3

Yes

Sample Input 4

ABBBBBBBBBBBBBCCCCCC

Sample Output 4

Yes

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N and integers L and R such that L\leq R.

For each i=1,2,\ldots,N, find the integer X_i that satisfies both of the following conditions. Note that the integer to be found is always uniquely determined.

• L\leq X_i \leq R.
• For every integer Y such that L \leq Y \leq R, it holds that |X_i - A_i| \leq |Y - A_i|.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq L\leq R \leq 10^9
• 1\leq A_i\leq 10^9
• All input values are integers.

Sample Input 1

5 4 7
3 1 4 9 7

Sample Output 1

4 4 4 7 7

For i=1:

• |4-3|=1
• |5-3|=2
• |6-3|=3
• |7-3|=4

Thus, X_i = 4.

Sample Input 2

3 10 10
11 10 9

Sample Output 2

10 10 10

Problem Statement

For two strings A and B, let A+B denote the concatenation of A and B in this order.

You are given N strings S_1,\ldots,S_N. Modify and print them as follows, in the order i=1, \ldots, N:

• if none of S_1,\ldots,S_{i-1} is equal to S_i, print S_i;
• if X (X>0) of S_1,\ldots,S_{i-1} are equal to S_i, print S_i+ ( +X+ ), treating X as a string.

Constraints

• 1 \leq N \leq 2\times 10^5
• S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.

Sample Input 1

5
newfile
newfile
newfolder
newfile
newfolder

Sample Output 1

newfile
newfile(1)
newfolder
newfile(2)
newfolder(1)

Sample Input 2

11
a
a
a
a
a
a
a
a
a
a
a

Sample Output 2

a
a(1)
a(2)
a(3)
a(4)
a(5)
a(6)
a(7)
a(8)
a(9)
a(10)

Problem Statement

You are given three sequences A=(A_1,\ldots,A_N), B=(B_1,\ldots,B_M), and C=(C_1,\ldots,C_L).

Additionally, a sequence X=(X_1,\ldots,X_Q) is given. For each i=1,\ldots,Q, solve the following problem:

Problem: Is it possible to select one element from each of A, B, and C so that their sum is X_i?

Constraints

• 1 \leq N,M,L \leq 100
• 0 \leq A_i, B_i ,C_i \leq 10^8
• 1 \leq Q \leq 2\times 10^5
• 0 \leq X_i \leq 3\times 10^8
• All input values are integers.

Sample Input 1

3
1 2 3
2
2 4
6
1 2 4 8 16 32
4
1 5 10 50

Sample Output 1

No
Yes
Yes
No

• It is impossible to select one element from each of A, B, and C so that their sum is 1.
• Selecting 1, 2, and 2 from A, B, and C, respectively, makes the sum 5.
• Selecting 2, 4, and 4 from A, B, and C, respectively, makes the sum 10.
• It is impossible to select one element from each of A, B, and C so that their sum is 50.

Problem Statement

You are given strings S and T consisting of lowercase English letters and ?. Here, |S| \gt |T| holds (for a string X, |X| denotes the length of X).

Two strings X and Y such that |X|=|Y| is said to match if and only if:

• one can make X equal Y by replacing each ? in X and Y with any English letter independently.

Solve the following problem for each x=0,1,\ldots,|T|:

• Let S' be the string of length |T| obtained by concatenating the first x characters and the last (|T|-x) characters of S without changing the order. Print Yes if S' and T match, and No otherwise.

Constraints

• S and T are strings consisting of lowercase English letters and ?.
• 1 \leq |T| \lt |S| \leq 3 \times 10^5

Sample Input 1

a?c
b?

Sample Output 1

Yes
No
No

When x=0, S' equals ?c. Here, we can replace the 1-st character of S', ?, with b and the 2-nd character of T, ?, with c to make S' equal T, so S' and T match. Thus, Yes should be printed in the first line.
When x=1 and 2, respectively, S' is ac and a?, neither of which matches with T. Thus, No should be printed in the second and third lines.

Sample Input 2

atcoder
?????

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes

Sample Input 3

beginner
contest

Sample Output 3

No
No
No
No
No
No
No
No

Problem Statement

You are given a length-N sequence A=(A_1,A_2,\dots,A_N) consisting of 0, 1, and 2, and a length-N string S=S_1S_2\dots S_N consisting of M, E, and X.

Find the sum of \text{mex}(A_i,A_j,A_k) over all tuples of integers (i,j,k) such that 1 \leq i < j < k \leq N and S_iS_jS_k= MEX. Here, \text{mex}(A_i,A_j,A_k) denotes the minimum non-negative integer that equals neither A_i,A_j, nor A_k.

Constraints

• 3\leq N \leq 2\times 10^5
• N is an integer.
• A_i \in \lbrace 0,1,2\rbrace
• S is a string of length N consisting of M, E, and X.

Sample Input 1

4
1 1 0 2
MEEX

Sample Output 1

3

The tuples (i,j,k)\ (1 \leq i < j < k \leq N) such that S_iS_jS_k = MEX are the following two: (i,j,k)=(1,2,4),(1,3,4). Since \text{mex}(A_1,A_2,A_4)=\text{mex}(1,1,2)=0 and \text{mex}(A_1,A_3,A_4)=\text{mex}(1,0,2)=3, the answer is 0+3=3.

Sample Input 2

3
0 0 0
XXX

Sample Output 2

0

Sample Input 3

15
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2
EXMMXXXEMEXEXMM

Sample Output 3

13

Problem Statement

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

You and the judge will follow the procedure below. The procedure consists of phases 1 and 2; phase 1 is immediately followed by phase 2.

(Phase 1)

• The judge decides an integer N between 1 and 10^9 (inclusive), which is hidden.
• You print an integer M between 1 and 110 (inclusive).
• You also print an integer sequence A=(A_1,A_2,\ldots,A_M) of length M such that 1 \leq A_i \leq M for all i = 1, 2, \ldots, M.

(Phase 2)

• The judge gives you an integer sequence B=(B_1,B_2,\ldots,B_M) of length M. Here, B_i = f^N(i). f(i) is defined by f(i)=A_i for all integers i between 1 and M (inclusive), and f^N(i) is the integer resulting from replacing i with f(i) N times.
• Based on the given B, you identify the integer N that the judge has decided, and print N.

After the procedure above, terminate the program immediately to be judged correct.

Constraints

• N is an integer between 1 and 10^9 (inclusive).

Input and Output

This is an interactive task, where your and the judge's programs interact via Standard Input and Output.

(Phase 1)

• First, print an integer M between 1 and 110 (inclusive). It must be followed by a newline.

M

• Then, print a sequence A=(A_1,A_2,\ldots,A_M) of length M consisting of integers between 1 and M (inclusive), with spaces in between. It must be followed by a newline.

A_1 A_2 \ldots A_M

(Phase 2)

• First, an integer sequence B=(B_1,B_2,\ldots,B_M) of length M is given from the input.

B_1 B_2 \ldots B_M

• Find the integer N and print it. It must be followed by a newline.

N

If you print something illegal, the judge prints -1. In that case, your submission is already considered incorrect. Since the judge program terminates at this point, it is desirable that your program terminates too.

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.
• After you print the answer (or you receive -1), immediately terminate the program normally. Otherwise, the verdict will be indeterminate.
• Note that an excessive newline is also considered an invalid input.

Sample Interaction

The following is a sample interaction with N = 2.