Problem Statement

This is the 214-th AtCoder Beginner Contest (ABC).

The ABCs so far have had the following number of problems.

• The 1-st through 125-th ABCs had 4 problems each.
• The 126-th through 211-th ABCs had 6 problems each.
• The 212-th through 214-th ABCs have 8 problems each.

Find the number of problems in the N-th ABC.

Constraints

• 1 \leq N \leq 214
• All values in input are integers.

Sample Input 1

214

Sample Output 1

8

Sample Input 2

1

Sample Output 2

4

Sample Input 3

126

Sample Output 3

6

Problem Statement

You are given a positive integer N.
Output the sum of all integers from 1 to N, that is, 1+2+\cdots+N.

Constraints

• 1 \leq N \leq 100
• N is an integer.

Sample Input 1

5

Sample Output 1

15

Since 1+2+3+4+5=15, output 15.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

29

Sample Output 3

435

Problem Statement

Let us call a string consisting of uppercase and lowercase English alphabets a wonderful string if all of the following conditions are satisfied:

• The string contains an uppercase English alphabet.
• The string contains a lowercase English alphabet.
• All characters in the string are pairwise distinct.

For example, AtCoder and Aa are wonderful strings, while atcoder and Perfect are not.

Given a string S, determine if S is a wonderful string.

Constraints

• 1 \le |S| \le 100
• S is a string consisting of uppercase and lowercase English alphabets.

Sample Input 1

AtCoder

Sample Output 1

Yes

AtCoder is a wonderful string because it contains an uppercase English alphabet, a lowercase English alphabet, and all characters in the string are pairwise distinct.

Sample Input 2

Aa

Sample Output 2

Yes

Note that A and a are different characters. This string is a wonderful string.

Sample Input 3

atcoder

Sample Output 3

No

It is not a wonderful string because it does not contain an uppercase English alphabet.

Sample Input 4

Perfect

Sample Output 4

No

It is not a wonderful string because the 2-nd and the 5-th characters are the same.

Problem Statement

AtCoder Inc. sells glasses and mugs.

Takahashi has a glass with a capacity of G milliliters and a mug with a capacity of M milliliters.
Here, G<M.

Initially, both the glass and the mug are empty.
After performing the following operation K times, determine how many milliliters of water are in the glass and the mug, respectively.

• When the glass is filled with water, that is, the glass contains exactly G milliliters of water, discard all the water from the glass.
• Otherwise, if the mug is empty, fill the mug with water.
• Otherwise, transfer water from the mug to the glass until the mug is empty or the glass is filled with water.

Constraints

• 1\leq K\leq 100
• 1\leq G<M\leq 1000
• G, M, and K are integers.

Sample Input 1

5 300 500

Sample Output 1

200 500

The operation will be performed as follows. Initially, both the glass and the mug are empty.

• Fill the mug with water. The glass has 0 milliliters, and the mug has 500 milliliters of water.
• Transfer water from the mug to the glass until the glass is filled. The glass has 300 milliliters, and the mug has 200 milliliters of water.
• Discard all the water from the glass. The glass has 0 milliliters, and the mug has 200 milliliters of water.
• Transfer water from the mug to the glass until the mug is empty. The glass has 200 milliliters, and the mug has 0 milliliters of water.
• Fill the mug with water. The glass has 200 milliliters, and the mug has 500 milliliters of water.

Thus, after five operations, the glass has 200 milliliters, and the mug has 500 milliliters of water. Hence, print 200 and 500 in this order, separated by a space.

Sample Input 2

5 100 200

Sample Output 2

0 0

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a positive integer K.

Find the sum of the integers between 1 and K, inclusive, that do not appear in the sequence A.

Constraints

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

Sample Input 1

4 5
1 6 3 1

Sample Output 1

11

Among the integers between 1 and 5, three numbers, 2, 4, and 5, do not appear in A.

Thus, print their sum: 2+4+5=11.

Sample Input 2

1 3
346

Sample Output 2

6

Sample Input 3

10 158260522
877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739

Sample Output 3

12523196466007058

Problem Statement

There are N mochi (rice cakes) arranged in ascending order of size. The size of the i-th mochi (1 \leq i \leq N) is A_i.

Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.

You choose two mochi out of the N mochi, and place one on top of the other to form one kagamimochi.

Find how many different kinds of kagamimochi can be made.

Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• A_i \leq A_{i+1} \ (1 \leq i < N)
• All input values are integers.

Sample Input 1

6
2 3 4 4 7 10

Sample Output 1

8

The sizes of the given mochi are as follows:

In this case, you can make the following eight kinds of kagamimochi:

Note that there are two kinds of kagamimochi where a mochi of size 4 is topped by a mochi of size 2, and two kinds where a mochi of size 10 is topped by a mochi of size 4.

Sample Input 2

3
387 388 389

Sample Output 2

0

It is possible that you cannot make any kagamimochi.

Sample Input 3

32
1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641

Sample Output 3

388

Problem Statement

You are given a tree with N vertices numbered 1,2,\dots,N. The i-th edge connects vertices U_i and V_i.
Each vertex i has an integer A_i written on it.

Answer the following problem for all k=1,2,\dots,N.

• Problem: Among the vertices on the simple path (a path that does not visit the same vertex more than once) from vertex 1 to vertex k, if there exist two distinct vertices with the same integer written on them, output Yes; otherwise, output No.
  • It can be proved that the simple path connecting two vertices on a tree is unique.

Constraints

• All input values are integers.
• 2 \le N \le 2 \times 10^5
• 1 \le A_i \le 10^9
• 1 \le U_i, V_i \le N
• The given graph is a tree.

Sample Input 1

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

Sample Output 1

No
No
No
Yes
Yes

• For k=1: the path from vertex 1 to vertex 1 contains only vertex 1. Since the path consists of only one vertex, the answer is No.
• For k=2: the path from vertex 1 to vertex 2 contains vertices 1,2, with integers 1,3 written on them respectively. Thus, the answer is No.
• For k=3: the path from vertex 1 to vertex 3 contains vertices 1,3, with integers 1,2 written on them respectively. Thus, the answer is No.
• For k=4: the path from vertex 1 to vertex 4 contains vertices 1,3,4, with integers 1,2,1 written on them respectively. Since vertices 1 and 4 on the path have the same integer 1 written on them, the answer is Yes.
• For k=5: the path from vertex 1 to vertex 5 contains vertices 1,3,5, with integers 1,2,2 written on them respectively. Since vertices 3 and 5 on the path have the same integer 2 written on them, the answer is Yes.

Sample Input 2

2
1000000000 1000000000
2 1

Sample Output 2

No
Yes

Sample Input 3

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

Sample Output 3

No
Yes
Yes
Yes
Yes
No
No
No
No
Yes

Problem Statement

Given are a tree with N vertices, a sequence of M numbers A=(A_1,\ldots,A_M), and an integer K.
The vertices are numbered 1 through N, and the i-th edge connects Vertices U_i and V_i.

We will paint each of the N-1 edges of this tree red or blue. Among the 2^{N-1} such ways, find the number of ones that satisfies the following condition, modulo 998244353.

Condition:
Let us put a piece on Vertex A_1, and for each i=1,\ldots,M-1 in this order, move it from Vertex A_i to Vertex A_{i+1} along the edges in the shortest path. After all of these movements, R-B=K holds, where R and B are the numbers of times the piece traverses a red edge and a blue edge, respectively.

Constraints

• 2 \leq N \leq 1000
• 2 \leq M \leq 100
• |K| \leq 10^5
• 1 \leq A_i \leq N
• 1\leq U_i,V_i\leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

4 5 0
2 3 2 1 4
1 2
2 3
3 4

Sample Output 1

2

If we paint the 1-st and 3-rd edges red and the 2-nd edge blue, the piece will traverse the following numbers of red and blue edges:

• 0 red edges and 1 blue edge when moving from Vertex 2 to 3,
• 0 red edges and 1 blue edge when moving from Vertex 3 to 2,
• 1 red edge and 0 blue edges when moving from Vertex 2 to 1,
• 2 red edges and 1 blue edge when moving from Vertex 1 to 4,

for a total of 3 red edges and 3 blue edges, satisfying the condition.

Another way to satisfy the condition is to paint the 1-st and 3-rd edges blue and the 2-nd edge red. There is no other way to satisfy it, so the answer is 2.

Sample Input 2

3 10 10000
1 2 1 2 1 2 2 1 1 2
1 2
1 3

Sample Output 2

0

There may be no way to paint the tree to satisfy the condition.

Sample Input 3

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

Sample Output 3

126

Sample Input 4

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

Sample Output 4

2

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.