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

There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.

The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.

Determine whether the majority agrees with the proposal.

Constraints

• N is an odd number between 1 and 99, inclusive.
• S_i = For or S_i = Against, for all i = 1, 2, \dots, N.

Sample Input 1

3
For
Against
For

Sample Output 1

Yes

The proposal is supported by two people, which is the majority, so Yes should be printed.

Sample Input 2

5
Against
Against
For
Against
For

Sample Output 2

No

The proposal is supported by two people, which is not the majority, so No should be printed.

Sample Input 3

1
For

Sample Output 3

Yes

Problem Statement

Locate a piece on a chessboard.

We have a grid with 8 rows and 8 columns of squares. Each of the squares has a 2-character name determined as follows.

• The first character of the name of a square in the 1-st column from the left is a. Similarly, the first character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th column from the left is b, c, d, e, f, g, h, respectively.
• The second character of the name of a square in the 1-st row from the bottom is 1. Similarly, the second character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th row from the bottom is 2, 3, 4, 5, 6, 7, 8, respectively.

For instance, the bottom-left square is named a1, the bottom-right square is named h1, and the top-right square is named h8.

You are given 8 strings S_1,\ldots,S_8, each of length 8, representing the state of the grid.
The j-th character of S_i is * if the square at the i-th row from the top and j-th column from the left has a piece on it, and . otherwise. The character * occurs exactly once among S_1,\ldots,S_8. Find the name of the square that has a piece on it.

Constraints

• S_i is a string of length 8 consisting of . and*.
• The character * occurs exactly once among S_1,\ldots,S_8.

Sample Input 1

........
........
........
........
........
........
........
*.......

Sample Output 1

a1

As explained in the problem statement, the bottom-left square is named a1.

Sample Input 2

........
........
........
........
........
.*......
........
........

Sample Output 2

b3

Problem Statement

There are 7 points A, B, C, D, E, F, and G on a straight line, in this order. (See also the figure below.)
The distances between adjacent points are as follows.

• Between A and B: 3
• Between B and C: 1
• Between C and D: 4
• Between D and E: 1
• Between E and F: 5
• Between F and G: 9

You are given two uppercase English letters p and q. Each of p and q is A, B, C, D, E, F, or G, and it holds that p \neq q.
Find the distance between the points p and q.

Constraints

• Each of p and q is A,B,C,D,E,F, or G.
• p \neq q

Sample Input 1

A C

Sample Output 1

4

The distance between the points A and C is 3 + 1 = 4.

Sample Input 2

G B

Sample Output 2

20

The distance between the points G and B is 9 + 5 + 1 + 4 + 1 = 20.

Sample Input 3

C F

Sample Output 3

10

Problem Statement

You are given N strings S_1,S_2,\dots,S_N, each of length M, consisting of lowercase English letter. Here, S_i are pairwise distinct.

Determine if one can rearrange these strings to obtain a new sequence of strings T_1,T_2,\dots,T_N such that:

• for all integers i such that 1 \le i \le N-1, one can alter exactly one character of T_i to another lowercase English letter to make it equal to T_{i+1}.

Constraints

• 2 \le N \le 8
• 1 \le M \le 5
• S_i is a string of length M consisting of lowercase English letters. (1 \le i \le N)
• S_i are pairwise distinct.

Sample Input 1

4 4
bbed
abcd
abed
fbed

Sample Output 1

Yes

One can rearrange them in this order: abcd, abed, bbed, fbed. This sequence satisfies the condition.

Sample Input 2

2 5
abcde
abced

Sample Output 2

No

No matter how the strings are rearranged, the condition is never satisfied.

Sample Input 3

8 4
fast
face
cast
race
fact
rice
nice
case

Sample Output 3

Yes

Problem Statement

Among the positive integers that consist of 0's and 2's when written in base 10, find the K-th smallest integer.

Constraints

• K is an integer between 1 and 10^{18} (inclusive).

Sample Input 1

3

Sample Output 1

22

The positive integers that consist of 0's and 2's when written in base 10 are 2,20,22,\dots in ascending order.
The (K=) 3-rd of them, which is 22, should be printed.

Sample Input 2

11

Sample Output 2

2022

Sample Input 3

923423423420220108

Sample Output 3

220022020000202020002022022000002020002222002200002022002200

Note that the exact value of the answer must be printed as an integer, even if it is big.

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

Given is a weighted undirected connected graph G with N vertices and M edges, which may contain self-loops and multi-edges.
The vertices are labeled as Vertex 1, Vertex 2, \dots, Vertex N.
The edges are labeled as Edge 1, Edge 2, \ldots, Edge M. Edge i connects Vertex a_i and Vertex b_i and has a weight of c_i. Here, for every pair of integers (i, j) such that 1 \leq i \lt j \leq M, c_i \neq c_j holds.

Process the Q queries explained below.
The i-th query gives a triple of integers (u_i, v_i, w_i). Here, for every integer j such that 1 \leq j \leq M, w_i \neq c_j holds.
Let e_i be an undirected edge that connects Vertex u_i and Vertex v_i and has a weight of w_i. Consider the graph G_i obtained by adding e_i to G. It can be proved that the minimum spanning tree T_i of G_i is uniquely determined. Does T_i contain e_i? Print the answer as Yes or No.

Note that the queries do not change T. In other words, even though Query i considers the graph obtained by adding e_i to G, the G in other queries does not have e_i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N - 1 \leq M \leq 2 \times 10^5
• 1 \leq a_i \leq N (1 \leq i \leq M)
• 1 \leq b_i \leq N (1 \leq i \leq M)
• 1 \leq c_i \leq 10^9 (1 \leq i \leq M)
• c_i \neq c_j (1 \leq i \lt j \leq M)
• The graph G is connected.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq u_i \leq N (1 \leq i \leq Q)
• 1 \leq v_i \leq N (1 \leq i \leq Q)
• 1 \leq w_i \leq 10^9 (1 \leq i \leq Q)
• w_i \neq c_j (1 \leq i \leq Q, 1 \leq j \leq M)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes
No
Yes

Below, let (u,v,w) denote an undirected edge that connects Vertex u and Vertex v and has the weight of w. Here is an illustration of G:

For example, Query 1 considers the graph G_1 obtained by adding e_1 = (1,3,1) to G. The minimum spanning tree T_1 of G_1 has the edge set \lbrace (1,2,2),(1,3,1),(2,4,5),(3,5,8) \rbrace, which contains e_1, so Yes should be printed.

Sample Input 2

2 3 2
1 2 100
1 2 1000000000
1 1 1
1 2 2
1 1 5

Sample Output 2

Yes
No

Problem Statement

You are given an integer array A=(a_1,a_2,\ldots,a_N).
You may perform the following operation any number of times (possibly zero).

• Choose a nonempty contiguous subarray of A, and delete it from the array.

For each x=1,2,\ldots,M, solve the following problem:

• Find the minimum possible number of operations to make the sum of elements of A equal x. If it is impossible to make the sum of elements of A equal x, print -1 instead.

Note that the sum of elements of an empty array is 0.

Constraints

• 1 \leq N,M \leq 3000
• 1 \leq a_i \leq 3000
• All values in the input are integers.

Sample Input 1

4 5
1 2 3 4

Sample Output 1

1
2
1
1
1

The followings are examples of minimum number of operations that achieve the goal.

• For x=1, delete a_2,a_3,a_4, and the sum of elements of A becomes x.
• For x=2, delete a_3,a_4, then delete a_1, and the sum of elements of A becomes x.
• For x=3, delete a_3,a_4, and the sum of elements of A becomes x.
• For x=4, delete a_1,a_2,a_3, and the sum of elements of A becomes x.
• For x=5, delete a_2,a_3, and the sum of elements of A becomes x.

Sample Input 2

1 5
3

Sample Output 2

-1
-1
0
-1
-1

Sample Input 3

12 20
2 5 6 5 2 1 7 9 7 2 5 5

Sample Output 3

2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1