Problem Statement

A mayoral election is being held in AtCoder City. The candidates are Takahashi and Aoki.

There are N valid votes cast for either of the two candidates, and the counting is currently underway. Here, N is an odd number.

The current vote count is T votes for Takahashi and A votes for Aoki.

Determine if the outcome of the election is already decided at this point.

Constraints

• 1 \leq N \leq 99
• N is an odd number.
• 0 \leq T, A \leq N
• T + A \leq N
• All input values are integers.

Sample Input 1

7 4 2

Sample Output 1

Yes

Even if the remaining one vote goes to Aoki, Takahashi will still win. That is, his victory is decided, so print Yes.

Sample Input 2

99 12 48

Sample Output 2

No

Although Aoki currently has more votes, Takahashi would win if he receives the remaining 39 votes. Therefore, print No.

Sample Input 3

1 0 0

Sample Output 3

No

Problem Statement

You are given a horizontally written text. Convert it to vertical writing, filling spaces with *.

You are given N strings S_1, S_2, \dots, S_N consisting of lowercase English letters. Let M be the maximum length of these strings.

Print M strings T_1, T_2, \dots, T_M that satisfy the following conditions:

• Each T_i consists of lowercase English letters and *.
• Each T_i does not end with *.
• For each 1 \leq i \leq N, the following holds:
  • For each 1 \leq j \leq |S_i|, the (N-i+1)-th character of T_j exists, and the concatenation of the (N-i+1)-th characters of T_1, T_2, \dots, T_{|S_i|} in this order equals S_i.
  • For each |S_i| + 1 \leq j \leq M, the (N-i+1)-th character of T_j either does not exist or is *.

Here, |S_i| denotes the length of the string S_i.

Constraints

• N is an integer between 1 and 100, inclusive.
• Each S_i is a string of lowercase English letters with length between 1 and 100, inclusive.

Sample Input 1

3
abc
de
fghi

Sample Output 1

fda
geb
h*c
i

Placing * as the 2nd character of T_3 puts the c in the correct position. On the other hand, placing * as the 2nd and 3rd characters of T_4 would make T_4 end with *, which violates the condition.

Sample Input 2

3
atcoder
beginner
contest

Sample Output 2

cba
oet
ngc
tio
end
sne
ter
*r

Problem Statement

You have an empty bag. You are given Q queries, which must be processed in order.

There are three types of queries.

• 1 x : Put one ball with the integer x written on it into the bag.
• 2 x : Remove one ball with the integer x written on it from the bag and discard it. It is guaranteed that the bag has a ball with the integer x written on it when this query is given.
• 3 : Print the number of different integers written on the balls in the bag.

Constraints

• 1 \leq Q \leq 2 \times 10^{5}
• 1 \leq x \leq 10^{6}
• When a query of the second type is given, the bag has a ball with the integer x written on it.
• There is at least one query of the third type.
• All input values are integers.

Sample Input 1

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

Sample Output 1

3
2
3

Initially, the bag is empty.

For the first query 1 3, a ball with the integer 3 written on it enters the bag.

For the second query 1 1, a ball with the integer 1 written on it enters the bag.

For the third query 1 4, a ball with the integer 4 written on it enters the bag.

For the fourth query 3, the bag has balls with the integers 1, 3, 4, so print 3.

For the fifth query 2 1, a ball with the integer 1 written on it is removed from the bag.

For the sixth query 3, the bag has balls with the integers 3, 4, so print 2.

For the seventh query 1 5, a ball with the integer 5 written on it enters the bag.

For the eighth query 3, the bag has balls with the integers 3, 4, 5, so print 3.

Sample Input 2

8
1 2
1 2
3
2 2
1 4
1 4
2 2
3

Sample Output 2

1
1

Problem Statement

You are given a positive integer N, and an integer A_{x,y,z} for each triple of integers (x, y, z) such that 1 \leq x, y, z \leq N.

You will be given Q queries in the following format, which must be processed in order.

For the i-th query (1 \leq i \leq Q), you are given a tuple of integers (Lx_i, Rx_i, Ly_i, Ry_i, Lz_i, Rz_i) such that 1 \leq Lx_i \leq Rx_i \leq N, 1 \leq Ly_i \leq Ry_i \leq N, and 1 \leq Lz_i \leq Rz_i \leq N. Find:

\displaystyle{\sum_{x=Lx_i}^{Rx_i} \sum_{y=Ly_i}^{Ry_i} \sum_{z=Lz_i}^{Rz_i} A_{x,y,z}}.

Constraints

• 1 \leq N \leq 100
• 1 \leq Q \leq 2 \times 10^{5}
• 0 \leq A_{x,y,z} \leq 999 (1 \leq x, y, z \leq N)
• 1 \leq Lx_i \leq Rx_i \leq N (1 \leq i \leq Q)
• 1 \leq Ly_i \leq Ry_i \leq N (1 \leq i \leq Q)
• 1 \leq Lz_i \leq Rz_i \leq N (1 \leq i \leq Q)
• All input values are integers.

Sample Input 1

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

Sample Output 1

10
26

For the 1st query, the sought value is A_{1,2,1} + A_{2,2,1} = 3 + 7 = 10. Thus, print 10.

For the 2nd query, the sought value is A_{2,1,1} + A_{2,1,2} + A_{2,2,1} + A_{2,2,2} = 5 + 6 + 7 + 8 = 26. Thus, print 26.

Sample Input 2

3
733 857 714
956 208 257
123 719 648
840 881 245
245 112 746
306 942 694
58 870 849
13 208 789
687 906 783
8
3 3 3 3 1 1
1 3 2 3 3 3
2 2 2 3 1 1
1 3 1 1 1 1
2 3 2 3 2 3
1 2 1 1 1 2
3 3 2 2 1 3
1 2 2 3 2 3

Sample Output 2

687
3917
551
1631
5180
3311
1010
4326

Problem Statement

You are given N points (x_1, y_1), (x_2, y_2), \dots, (x_N, y_N) on a two-dimensional plane, and a non-negative integer D.

Find the number of integer pairs (x, y) such that \displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq D \leq 10^6
• -10^6 \leq x_i, y_i \leq 10^6
• (x_i, y_i) \neq (x_j, y_j) for i \neq j.
• All input values are integers.

Sample Input 1

2 3
0 0
1 0

Sample Output 1

8

The following figure visualizes the input and the answer for Sample 1. The blue points represent the input. The blue and red points, eight in total, satisfy the condition in the statement.

Sample Input 2

2 0
0 0
2 0

Sample Output 2

0

Sample Input 3

6 100
9 -6
10 -1
2 10
-1 7
-7 5
-1 -4

Sample Output 3

419

Problem Statement

You are given N linear functions f_1, f_2, \ldots, f_N, where f_i(x) = A_i x + B_i.

Find the maximum possible value of f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots )) for a sequence p = (p_1, p_2, \ldots, p_K) of K distinct integers between 1 and N, inclusive.

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq K \leq \text{min}(N,10)
• 1 \leq A_i, B_i \leq 50 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3 2
2 3
1 5
4 2

Sample Output 1

26

Here are all possible p and the corresponding values of f_{p_1}(f_{p_2}(1)):

• p= ( 1,2 ) : f_1(f_2(1))=15
• p= ( 1,3 ) : f_1(f_3(1))=15
• p= ( 2,1 ) : f_2(f_1(1))=10
• p= ( 2,3 ) : f_2(f_3(1))=11
• p= ( 3,1 ) : f_3(f_1(1))=22
• p= ( 3,2 ) : f_3(f_2(1))=26

Therefore, print 26.

Sample Input 2

10 3
48 40
34 22
24 37
45 40
48 31
49 44
45 40
44 6
35 22
39 28

Sample Output 2

216223

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The i-th edge connects vertices u_i and v_i bidirectionally.

Determine if there exists a way to write an integer between 1 and 2^{60} - 1, inclusive, on each vertex of this graph so that the following condition is satisfied:

• For every vertex v with a degree of at least 1, the total XOR of the numbers written on its adjacent vertices (excluding v itself) is 0.

Constraints

• 1 \leq N \leq 60
• 0 \leq M \leq N(N-1)/2
• 1 \leq u_i < v_i \leq N
• (u_i, v_i) \neq (u_j, v_j) for i \neq j.
• All input values are integers.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

Yes
4 4 4

Other acceptable solutions include writing (2,2,2) or (3,3,3).

Sample Input 2

2 1
1 2

Sample Output 2

No

Sample Input 3

1 0

Sample Output 3

Yes
1

Any integer between 1 and 2^{60} - 1 can be written.

Sample Input 4

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

Sample Output 4

Yes
12 4 4 8