Problem Statement

You are given N strings.

The i-th string S_i (1 \leq i \leq N) is either Takahashi or Aoki.

How many i are there such that S_i is equal to Takahashi?

Constraints

• 1 \leq N \leq 100
• N is an integer.
• Each S_i is Takahashi or Aoki. (1 \leq i \leq N)

Sample Input 1

3
Aoki
Takahashi
Takahashi

Sample Output 1

2

S_2 and S_3 are equal to Takahashi, while S_1 is not.

Therefore, print 2.

Sample Input 2

2
Aoki
Aoki

Sample Output 2

0

It is possible that no S_i is equal to Takahashi.

Sample Input 3

20
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

Sample Output 3

7

Problem Statement

The AtCoder railway line has N stations, numbered 1, 2, \ldots, N.

On this line, there are inbound trains that start at station 1 and stop at the stations 2, 3, \ldots, N in order, and outbound trains that start at station N and stop at the stations N - 1, N - 2, \ldots, 1 in order.

Takahashi is about to travel from station X to station Y using only one of the inbound and outbound trains.

Determine whether the train stops at station Z during this travel.

Constraints

• 3 \leq N \leq 100
• 1 \leq X, Y, Z \leq N
• X, Y, and Z are distinct.
• All input values are integers.

Sample Input 1

7 6 1 3

Sample Output 1

Yes

To travel from station 6 to station 1, Takahashi will take an outbound train.

After departing from station 6, the train stops at stations 5, 4, 3, 2, 1 in order, which include station 3, so you should print Yes.

Sample Input 2

10 3 2 9

Sample Output 2

No

Sample Input 3

100 23 67 45

Sample Output 3

Yes

Problem Statement

N people, person 1, person 2, \ldots, person N, are playing roulette. The outcome of a spin is one of the 37 integers from 0 to 36. For each i = 1, 2, \ldots, N, person i has bet on C_i of the 37 possible outcomes: A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i}.

The wheel has been spun, and the outcome is X. Print the numbers of all people who have bet on X with the fewest bets, in ascending order.

More formally, print all integers i between 1 and N, inclusive, that satisfy both of the following conditions, in ascending order:

• Person i has bet on X.
• For each j = 1, 2, \ldots, N, if person j has bet on X, then C_i \leq C_j.

Note that there may be no number to print (see Sample Input 2).

Constraints

• 1 \leq N \leq 100
• 1 \leq C_i \leq 37
• 0 \leq A_{i, j} \leq 36
• A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i} are all different for each i = 1, 2, \ldots, N.
• 0 \leq X \leq 36
• All input values are integers.

Sample Input 1

4
3
7 19 20
4
4 19 24 0
2
26 10
3
19 31 24
19

Sample Output 1

2
1 4

The wheel has been spun, and the outcome is 19. The people who has bet on 19 are person 1, person 2, and person 4, and the number of their bets are 3, 4, and 3, respectively. Therefore, among the people who has bet on 19, the ones with the fewest bets are person 1 and person 4.

Sample Input 2

3
1
1
1
2
1
3
0

Sample Output 2

0

The wheel has been spun and the outcome is 0, but no one has bet on 0, so there is no number to print.

Problem Statement

You are given an integer N and a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

Given Q queries, process them in the given order. Each query is of one of the following two kinds:

• 1 k x : set the value A _ k to x.
• 2 k : print the value A _ k.

Constraints

• 1 \leq N \leq 10 ^ 5
• 1 \leq Q \leq 10 ^ 5
• 0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
• 1\leq k\leq N for all queries.
• 0\leq x\leq 10 ^ 9 for all queries of the first kind.
• There is at least one query of the second kind.
• All values in the input are integers.

Sample Input 1

3
1 3 5
7
2 2
2 3
1 3 0
2 3
1 2 8
2 2
2 1

Sample Output 1

3
5
0
8
1

Initially, A=(1,3,5).

• For the 1-st query, A=(1,3,5), where A _ 2=3, so 3 should be printed.
• For the 2-nd query, A=(1,3,5), where A _ 3=5, so 5 should be printed.
• The 3-rd query sets the value A _ 3 to 0, making A=(1,3,0).
• For the 4-th query, A=(1,3,0), where A _ 3=0, so 0 should be printed.
• The 5-th query sets the value A _ 2 to 8, making A=(1,8,0).
• For the 6-th query, A=(1,8,0), where A _ 2=8, so 8 should be printed.
• For the 7-th query, A=(1,8,0), where A _ 1=1, so 1 should be printed.

Sample Input 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

Sample Output 2

2
16
0
0
16
100

Sample Input 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

Sample Output 3

478
317
838
838
176
595
468

Problem Statement

Takahashi decided to hold a programming contest.

The contest consists of five problems: A, B, C, D, E, with scores a, b, c, d, e, respectively.

There are 31 participants, and all of them solved at least one problem.

More specifically, for every non-empty subsequence (not necessarily contiguous) of the string ABCDE, there is a participant named after that subsequence who solved the problems corresponding to the letters in their name and did not solve the other problems.

For example, participant A solved only problem A, and participant BCE solved problems B, C, and E.

Print the names of the participants in order of their obtained scores, from the largest to the smallest. The score obtained by a participant is the sum of the scores of the problems they solved.

If two participants obtained the same score, print the one whose name is lexicographically smaller first.

Constraints

• 100\leq a\leq b\leq c\leq d\leq e\leq 2718
• All input values are integers.

Sample Input 1

400 500 600 700 800

Sample Output 1

ABCDE
BCDE
ACDE
ABDE
ABCE
ABCD
CDE
BDE
ADE
BCE
ACE
BCD
ABE
ACD
ABD
ABC
DE
CE
BE
CD
AE
BD
AD
BC
AC
AB
E
D
C
B
A

The score of each participant is as follows:

For example, ADE and BCE obtained the same score, and ADE is lexicographically smaller, so print ADE before BCE.

Sample Input 2

800 800 900 900 1000

Sample Output 2

ABCDE
ACDE
BCDE
ABCE
ABDE
ABCD
CDE
ACE
ADE
BCE
BDE
ABE
ACD
BCD
ABC
ABD
CE
DE
AE
BE
CD
AC
AD
BC
BD
AB
E
C
D
A
B

Sample Input 3

128 256 512 1024 2048

Sample Output 3

ABCDE
BCDE
ACDE
CDE
ABDE
BDE
ADE
DE
ABCE
BCE
ACE
CE
ABE
BE
AE
E
ABCD
BCD
ACD
CD
ABD
BD
AD
D
ABC
BC
AC
C
AB
B
A

Problem Statement

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

• 1\leq D \leq 2\times 10^{12}
• All input values are integers.

Sample Input 1

21

Sample Output 1

1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

0

Sample Input 3

264428617

Sample Output 3

32

Problem Statement

We have a polynomial of degree N, A(x)=A_Nx^N+A_{N-1}x^{N-1}+\cdots +A_1x+A_0,
and another of degree M, B(x)=B_Mx^M+B_{M-1}x^{M-1}+\cdots +B_1x+B_0.
Here, each coefficient of A(x) and B(x) is an integer whose absolute value is at most 100, and the leading coefficients are not 0.

Also, let the product of them be C(x)=A(x)B(x)=C_{N+M}x^{N+M}+C_{N+M-1}x^{N+M-1}+\cdots +C_1x+C_0.

Given A_0,A_1,\ldots, A_N and C_0,C_1,\ldots, C_{N+M}, find B_0,B_1,\ldots, B_M.
Here, the given inputs guarantee that there is a unique sequence B_0, B_1, \ldots, B_M that satisfies the given conditions.

Constraints

• 1 \leq N < 100
• 1 \leq M < 100
• |A_i| \leq 100
• |C_i| \leq 10^6
• A_N \neq 0
• C_{N+M} \neq 0
• There is a unique sequence B_0, B_1, \ldots, B_M that satisfies the conditions given in the statement.

Sample Input 1

1 2
2 1
12 14 8 2

Sample Output 1

6 4 2

For A(x)=x+2 and B(x)=2x^2+4x+6, we have C(x)=A(x)B(x)=(x+2)(2x^2+4x+6)=2x^3+8x^2+14x+12, so B(x)=2x^2+4x+6 satisfies the given conditions. Thus, B_0=6, B_1=4, B_2=2 should be printed in this order, with spaces in between.

Sample Input 2

1 1
100 1
10000 0 -1

Sample Output 2

100 -1

We have A(x)=x+100, C(x)=-x^2+10000, for which B(x)=-x+100 satisfies the given conditions. Thus, 100, -1 should be printed in this order, with spaces in between.

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges (a simple graph contains no self-loop and no multi-edges).
For i = 1, 2, \ldots, M, the i-th edge connects vertex u_i and vertex v_i bidirectionally.

Determine whether there is a way to paint each vertex black or white to satisfy both of the following conditions, and show one such way if it exists.

• At least one vertex is painted black.
• For every i = 1, 2, \ldots, K, the following holds:
  • the minimum distance between vertex p_i and a vertex painted black is exactly d_i.

Here, the distance between vertex u and vertex v is the minimum number of edges in a path connecting u and v.

Constraints

• 1 \leq N \leq 2000
• N-1 \leq M \leq \min\lbrace N(N-1)/2, 2000 \rbrace
• 1 \leq u_i, v_i \leq N
• 0 \leq K \leq N
• 1 \leq p_1 \lt p_2 \lt \cdots \lt p_K \leq N
• 0 \leq d_i \leq N
• The given graph is simple and connected.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

Yes
10100

One way to satisfy the conditions is to paint vertices 1, 3 black and vertices 2, 4, 5 white.
Indeed, for each i = 1, 2, 3, 4, 5, let A_i denote the minimum distance between vertex i and a vertex painted black, and we have (A_1, A_2, A_3, A_4, A_5) = (0, 1, 0, 1, 2), where A_1 = 0, A_5 = 2.

Sample Input 2

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

Sample Output 2

No

There is no way to satisfy the conditions by painting each vertex black or white, so you should print No.

Sample Input 3

1 0
0

Sample Output 3

Yes
1

Problem Statement

There is a circular cake divided into N pieces by cut lines. Each cut line is a line segment connecting the center of the circle to a point on the arc.

The pieces and cut lines are numbered 1, 2, \ldots, N in clockwise order, and piece i has a mass of A_i. Piece 1 is also called piece N + 1.

Cut line i is between pieces i and i + 1, and they are arranged clockwise in this order: piece 1, cut line 1, piece 2, cut line 2, \ldots, piece N, cut line N.

We want to divide this cake among K people under the following conditions. Let w_i be the sum of the masses of the pieces received by the i-th person.

• Each person receives one or more consecutive pieces.
• There are no pieces that no one receives.
• Under the above two conditions, \min(w_1, w_2, \ldots, w_K) is maximized.

Find the value of \min(w_1, w_2, \ldots, w_K) in a division that satisfies the conditions, and the number of cut lines that are never cut in the divisions that satisfy the conditions. Here, cut line i is considered cut if pieces i and i + 1 are given to different people.

Constraints

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

Sample Input 1

5 2
3 6 8 6 4

Sample Output 1

13 1

The following divisions satisfy the conditions:

• Give pieces 2, 3 to one person and pieces 4, 5, 1 to the other. Pieces 2, 3 have a total mass of 14, and pieces 4, 5, 1 have a total mass of 13.
• Give pieces 3, 4 to one person and pieces 5, 1, 2 to the other. Pieces 3, 4 have a total mass of 14, and pieces 5, 1, 2 have a total mass of 13.

The value of \min(w_1, w_2) in divisions satisfying the conditions is 13, and there is one cut line that is not cut in either division: cut line 5.

Sample Input 2

6 3
4 7 11 3 9 2

Sample Output 2

11 1

Sample Input 3

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

Sample Output 3

17 4