Problem Statement

Takahashi has N items and one bag.

The size of the i-th (1\le i\le N) item is A_i, and the size of the bag is M.

If and only if the total size of the items he is trying to put in the bag is at most M, he can put all those items in the bag simultaneously.

If he can put all N items in the bag simultaneously, print Yes; otherwise, print No.

Constraints

• 1\le N\le100
• 1\le M\le10000
• 1\le A_i\le100\ (1\le i\le N)
• All input values are integers.

Sample Input 1

5 15
3 1 4 1 5

Sample Output 1

Yes

The total size of the 5 items is 3+1+4+1+5=14. Since this is not greater than the bag size 15, Takahashi can put all items in the bag simultaneously. Thus, print Yes.

Sample Input 2

5 5
3 1 4 1 5

Sample Output 2

No

The total size of the 5 items is 14, which is greater than the bag size 5, so he cannot put all items in the bag simultaneously. Thus, print No.

Sample Input 3

1 10000
100

Sample Output 3

Yes

Problem Statement

You are given N types of strings S_1,S_2,\ldots,S_N.

You perform the following operation once:

• Choose distinct integers i and j\ (1\le i\le N,1\le j\le N) and concatenate S_i and S_j in this order.

How many different strings can be obtained as a result of this operation?

If different choices of (i,j) result in the same concatenated string, it is counted as one string.

Constraints

• 2\le N\le100
• N is an integer.
• S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters.
• S_i\ne S_j\ (1\le i\lt j\le N)

Sample Input 1

4
at
atco
coder
der

Sample Output 1

11

The possible strings are atatco, atcoat, atcoder, atcocoder, atder, coderat, coderatco, coderder, derat, deratco, dercoder, which are 11 strings.

Thus, print 11.

Sample Input 2

5
a
aa
aaa
aaaa
aaaaa

Sample Output 2

7

The possible strings are aaa, aaaa, aaaaa, aaaaaa, aaaaaaa, aaaaaaaa, aaaaaaaaa, which are 7 strings.

Thus, print 7.

Sample Input 3

10
armiearggc
ukupaunpiy
cogzmjmiob
rtwbvmtruq
qapfzsitbl
vhkihnipny
ybonzypnsn
esxvgoudra
usngxmaqpt
yfseonwhgp

Sample Output 3

90

Problem Statement

There is an empty integer sequence A=(). You are given Q queries, and you need to process them in the given order. There are two types of queries:

• Type 1: Given in the format 1 c x. Add c copies of x to the end of A.
• Type 2: Given in the format 2 k. Remove the first k elements from A and output the sum of the removed k integers. It is guaranteed that k is at most the length of A at that time.

Constraints

• 1 \leq Q \leq 2 \times 10^{5}
• In type 1 queries, 1 \leq c \leq 10^{9}.
• In type 1 queries, 1 \leq x \leq 10^{9}.
• In type 2 queries, letting n be the length of A at that time, 1 \leq k \leq \min(10^{9},n).
• All input values are integers.

Sample Input 1

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

Sample Output 1

11
19

• 1st query: Add 2 copies of 3 to the end of A. Then, A=(3,3).
• 2nd query: Add 4 copies of 5 to the end of A. Then, A=(3,3,5,5,5,5).
• 3rd query: Remove the first 3 elements from A. Then, the sum of the removed 3 integers is 3+3+5=11, so output 11. After removal, A=(5,5,5).
• 4th query: Add 6 copies of 2 to the end of A. Then, A=(5,5,5,2,2,2,2,2,2).
• 5th query: Remove the first 5 elements from A. Then, the sum of the removed 5 integers is 5+5+5+2+2=19, so output 19. After removal, A=(2,2,2,2).

Sample Input 2

10
1 75 22
1 81 72
1 2 97
1 84 82
1 2 32
1 39 57
2 45
1 40 16
2 32
2 42

Sample Output 2

990
804
3024

Sample Input 3

10
1 160449218 954291757
2 17217760
1 353195922 501899080
1 350034067 910748511
1 824284691 470338674
2 180999835
1 131381221 677959980
1 346948152 208032501
1 893229302 506147731
2 298309896

Sample Output 3

16430766442004320
155640513381884866
149721462357295680

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. It is guaranteed that for any i\ (1\le i\le N), A_i is not 0.

Determine whether there exists a permutation B=(B_1,B_2,\ldots,B_N) of A such that B forms a geometric sequence.

A sequence S=(S_1,S_2,\ldots,S_N) is a geometric sequence if there exists a real number r such that S_{i+1}=rS_i for all integers 1\le i\lt N.

Solve T test cases per input file.

Constraints

• 1\le T\le10^5
• 2\le N\le2\times10^5
• -10^9\le A_i\le10^9\ (1\le i\le N)
• A_i\ne0\ (1\le i\le N)
• The sum of N over all test cases in a single input file is at most 2\times10^5.
• All input values are integers.

Sample Input 1

3
5
1 8 2 4 16
5
-16 24 54 81 -36
7
90000 8100 -27000 729 -300000 -2430 1000000

Sample Output 1

Yes
No
Yes

In the first test case, the rearrangement (16,8,4,2,1) of A forms a geometric sequence with common ratio r=\frac{1}{2}. Thus, print Yes on the first line.

In the second test case, no rearrangement of A satisfies the condition. Thus, print No on the second line.

Problem Statement

You are given a permutation P=(P_0,P_1,\ldots,P_{2^{N}-1}) of (1,2,3,\ldots,2^{N}).

You can perform the following operation any number of times (possibly zero):

• Choose non-negative integers a,b satisfying 0 \leq a \times 2^{b} < (a+1) \times 2^{b} \leq 2^{N}, and reverse P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1}. Here, reversing P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} means simultaneously replacing P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} with P_{(a+1) \times 2^{b}-1}, P_{(a+1) \times 2^{b}-2},\ldots,P_{a \times 2^{b}}.

Find the lexicographically smallest permutation P that can be obtained by repeating the operation.

You are given T test cases, so find the answer for each.

Constraints

• 1 \leq T \leq 10^{5}
• 1 \leq N \leq 18
• P is a permutation of (1,2,3,\ldots,2^{N}).
• For each input file, the sum of 2^N over all test cases is at most 3 \times 10^{5}.
• All input values are integers.

Sample Input 1

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

Sample Output 1

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

In the first test case, when no operation is performed on P, P=(1,2). This is the lexicographically smallest permutation. Thus, the answer is (1,2).

In the second test case, when we perform the operation with a=1,b=1, P becomes (1,3,2,4). No matter how many operations we perform on P, we cannot obtain a permutation lexicographically smaller than (1,3,2,4). Thus, the answer is (1,3,2,4).

In the third test case, by performing operations in the following order, we can obtain P=(1,4,2,3):

• Perform the operation with a=0,b=1. P becomes (3,2,4,1).
• Perform the operation with a=0,b=2. P becomes (1,4,2,3).

No matter how many operations we perform on P, we cannot obtain a permutation lexicographically smaller than (1,4,2,3). Thus, the answer is (1,4,2,3).

Problem Statement

There is an H \times W grid. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. Among these, K cells are goals. The i-th goal (1 \leq i \leq K) is cell (R_i, C_i).

Takahashi and Aoki play a game using this grid and a single piece placed on the grid. Takahashi and Aoki repeatedly perform the following series of operations until the piece reaches a goal cell:

• Aoki chooses an integer a between 1 and 4, inclusive.
• Then, Takahashi chooses an integer b between 1 and 4, inclusive, where a \neq b must be satisfied. Let (i,j) be the cell where the piece is placed before the operation. Based on the chosen integer b and the piece's position, move the piece.
  • When b=1: If (i-1,j) is within the grid, move the piece from cell (i,j) to cell (i-1,j); if it is outside the grid, do nothing.
  • When b=2: If (i+1,j) is within the grid, move the piece from cell (i,j) to cell (i+1,j); if it is outside the grid, do nothing.
  • When b=3: If (i,j-1) is within the grid, move the piece from cell (i,j) to cell (i,j-1); if it is outside the grid, do nothing.
  • When b=4: If (i,j+1) is within the grid, move the piece from cell (i,j) to cell (i,j+1); if it is outside the grid, do nothing.

Takahashi's objective is to minimize the number of moves until the piece reaches a goal. Aoki's objective is to prevent the piece from reaching the goal; if that is impossible, his objective is to maximize the number of moves until the piece reaches a goal.

For all pairs of integers (i,j) satisfying 1 \leq i \leq H,1 \leq j \leq W, solve the following problem and find the sum of all solutions:

Start the game with the piece at cell (i,j). Assume both players act optimally toward their respective objectives. If Takahashi can make the piece reach a goal, the solution is the minimum number of moves; otherwise, the solution is 0.

Constraints

• 2 \leq H \leq 3000
• 2 \leq W \leq 3000
• 1 \leq K \leq \min(HW,3000)
• 1 \leq R_i \leq H
• 1 \leq C_i \leq W
• (R_i,C_i) \neq (R_j,C_j) (1 \leq i < j \leq K)
• All input values are integers.

Sample Input 1

2 3 2
1 2
2 1

Sample Output 1

2

When (i,j)=(1,2),(2,1), the starting cell is a goal, so the solution is 0.

When (i,j)=(1,1),(2,2), no matter which a Aoki chooses, Takahashi can make the piece reach a goal in 1 move from the starting cell, so the solution is 1.

When (i,j)=(1,3),(2,3), Takahashi cannot reach a goal, so the solution is 0.

The sum of these is 0 \times 2 + 1 \times 2 + 0 \times 2 = 2. Thus, print 2.

Sample Input 2

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

Sample Output 2

43

Sample Input 3

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

Sample Output 3

153

Problem Statement

There is an H \times W grid. Let (i,j) denote the cell at the i-th row (1\le i\le H) from the top and j-th column (1\le j\le W) from the left.

Each cell in the grid either has an obstacle placed on it or has nothing placed on it. There are K cells with obstacles: cells (r_1,c_1),(r_2,c_2),\ldots,(r_K,c_K).

Takahashi is initially at cell (1,1) and wants to reach cell (H,W) by repeatedly moving to an adjacent cell (up, down, left, right) that has nothing placed on it.

More precisely, he can repeat the following operation as many times as he likes:

• Choose one of the following four operations and perform the chosen operation:
  • If 1\lt i and cell (i-1,j) has nothing placed on it, move to cell (i-1,j). Otherwise, do not move.
  • If 1\lt j and cell (i,j-1) has nothing placed on it, move to cell (i,j-1). Otherwise, do not move.
  • If i\lt H and cell (i+1,j) has nothing placed on it, move to cell (i+1,j). Otherwise, do not move.
  • If j\lt W and cell (i,j+1) has nothing placed on it, move to cell (i,j+1). Otherwise, do not move.

Determine whether he can move from cell (1,1) to cell (H,W).

Constraints

• 1\le H\le2\times10^5
• 1\le W\le2\times10^5
• 0\le K\le2\times10^5
• 1\le r_i\le H\ (1\le i\le K)
• 1\le c_i\le W\ (1\le i\le K)
• (r_i,c_i)\ne(1,1)\ (1\le i\le K)
• (r_i,c_i)\ne(H,W)\ (1\le i\le K)
• (r_i,c_i)\ne(r_j,c_j)\ (1\le i\lt j\le K)
• All input values are integers.

Sample Input 1

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

Sample Output 1

No

The grid looks as follows:

Takahashi cannot move from cell (1,1) to cell (4,5).

Sample Input 2

2 7 3
1 2
2 4
1 6

Sample Output 2

Yes

The grid looks as follows:

He can move from cell (1,1) to cell (2,7) by moving as shown in the figure.

Sample Input 3

1 1 0

Sample Output 3

Yes

Note that there may be cases where he does not need to move or where no obstacles are placed.

Sample Input 4

10 12 20
8 3
1 11
6 4
3 7
10 4
5 7
4 7
5 5
4 3
6 1
1 6
2 7
6 7
1 3
6 3
2 12
9 6
7 3
3 11
9 7

Sample Output 4

Yes