Problem Statement

You are given a string S consisting of v and w.

Print the number of "bottoms" in the string S (see the figure at Sample Input/Output).

Constraints

• S is a string consisting of v and w.
• The length of S is between 1 and 100, inclusive.

Sample Input 1

vvwvw

Sample Output 1

7

The image above shows the seven "bottoms" in the string vvwvw.

Sample Input 2

v

Sample Output 2

1

Sample Input 3

wwwvvvvvv

Sample Output 3

12

Problem Statement

You are given positive integers X,Y,Z.

Takahashi and Aoki are currently X years old and Y years old, respectively.

Takahashi and Aoki age by 1 year simultaneously on every January 1st.

Determine whether there is a moment in the future (including this year) when Takahashi's age becomes exactly Z times Aoki's age.

Constraints

• 1\le X,Y \le 100
• 2\le Z\le 10
• All input values are integers.

Sample Input 1

44 20 2

Sample Output 1

Yes

Four years from now, Takahashi will be 48 years old and Aoki will be 24 years old, so Takahashi's age will be exactly twice Aoki's age. Thus, output Yes.

Sample Input 2

28 10 3

Sample Output 2

No

There will never be a moment when Takahashi's age becomes exactly three times Aoki's age. Thus, output No.

Sample Input 3

50 5 10

Sample Output 3

Yes

Currently, Takahashi's age is exactly 10 times Aoki's age.

Note that you need to determine whether there will be such a moment in the future including this year.

Sample Input 4

1 100 2

Sample Output 4

No

Problem Statement

Takahashi is trying to create a game inspired by baseball, but he is having difficulty writing the code.
Write a program for Takahashi that solves the following problem.

There are 4 squares called Square 0, Square 1, Square 2, and Square 3. Initially, all squares are empty.
There is also an integer P; initially, P = 0.
Given a sequence of positive integers A = (A_1, A_2, \dots, A_N), perform the following operations for i = 1, 2, \dots, N in this order:

1. Put a piece on Square 0.
2. Advance every piece on the squares A_i squares ahead. In other words, if Square x has a piece, move the piece to Square (x + A_i).
   If, however, the destination square does not exist (i.e. x + A_i is greater than or equal to 4) for a piece, remove it. Add to P the number of pieces that have been removed.

Print the value of P after all the operations have been performed.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 4
• All values in input are integers.

Sample Input 1

4
1 1 3 2

Sample Output 1

3

The operations are described below. After all the operations have been performed, P equals 3.

• The operations for i=1:
  1. Put a piece on Square 0. Now, Square 0 has a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Square 1 has a piece.
• The operations for i=2:
  1. Put a piece on Square 0. Now, Squares 0 and 1 have a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Squares 1 and 2 have a piece.
• The operations for i=3:
  1. Put a piece on Square 0. Now, Squares 0, 1, and 2 have a piece.
  2. Advance every piece on the squares 3 squares ahead.
     Here, for the pieces on Squares 1 and 2, the destination squares do not exist (since 1+3=4 and 2+3=5), so remove these pieces and add 2 to P. P now equals 2. After these moves, Square 3 has a piece.
• The operations for i=4:
  1. Put a piece on Square 0. Now, Squares 0 and 3 have a piece.
  2. Advance every piece on the squares 2 squares ahead.
     Here, for the piece on Square 3, the destination square does not exist (since 3+2=5), so remove this piece and add 1 to P. P now equals 3.
     After these moves, Square 2 has a piece.

Sample Input 2

3
1 1 1

Sample Output 2

0

The value of P may not be updated by the operations.

Sample Input 3

10
2 2 4 1 1 1 4 2 2 1

Sample Output 3

8

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

• N is an integer between 1 and 1000, inclusive.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

Problem Statement

You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).

Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.

Constraints

• 2 \leq N \leq 100
• 1 \leq P_i \leq N \, (1 \leq i \leq N)
• P_i \neq P_j \, (i \neq j)
• (P_1, \dots, P_N) \neq (1, \dots, N)
• All values in the input are integers.

Sample Input 1

3
3 1 2

Sample Output 1

2 3 1

Here are the permutations of (1, 2, 3) in ascending lexicographical order.

• (1, 2, 3)
• (1, 3, 2)
• (2, 1, 3)
• (2, 3, 1)
• (3, 1, 2)
• (3, 2, 1)

Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).

Sample Input 2

10
9 8 6 5 10 3 1 2 4 7

Sample Output 2

9 8 6 5 10 2 7 4 3 1

Problem Statement

You are given a sequence A of length N.
Freely choose exactly K elements from A and remove them, then concatenate the remaining elements in their original order to form a new sequence B.
Find the minimum possible value of this: the maximum value of B minus the minimum value of B.

Constraints

• All inputs are integers.
• 1 \le K < N \le 2 \times 10^5
• 1 \le A_i \le 10^9

Sample Input 1

5 2
3 1 5 4 9

Sample Output 1

2

Consider removing exactly two elements from A=(3,1,5,4,9).

• For example, if you remove the 2nd element 1 and the 5th element 9, the resulting sequence is B=(3,5,4).
  • In this case, the maximum value of B is 5 and the minimum value is 3, so (maximum value of B) - (minimum value of B) =2, which is the minimum possible value.

Sample Input 2

6 5
1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

8 3
31 43 26 6 18 36 22 13

Sample Output 3

18

Problem Statement

We have a horizontal cylinder. Given Q queries, process them in the given order.
Each query is of one of the following two types.

• 1 x c: Insert c balls, with a number x written on each of them, to the right end of the cylinder.
• 2 c: Take out the c leftmost balls contained in the cylinder and print the sum of the numbers written on the balls that have been taken out.

We assume that the balls do never change their order in the cylinder.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq 10^9
• Whenever a query of type 2 c is given, there are c or more balls in the cylinder.
• All values in input are integers.

Sample Input 1

4
1 2 3
2 2
1 3 4
2 3

Sample Output 1

4
8

• For the 1-st query, insert 3 balls, with a number 2 written on each of them, to the right end of the cylinder.
  The cylinder has now balls with numbers (2,2,2) written on them, from left to right.
• For the 2-nd query, take out the 2 leftmost balls contained in the cylinder.
  The numbers written on the balls taken out are 2,2, for a sum of 4, which should be printed. The cylinder has now a ball with a number (2) written on it, from left to right.
• For the 3-rd query, insert 4 balls, with a number 3 written on each of them, to the right end of the cylinder.
  The cylinder has now balls with numbers (2,3,3,3,3) written on them, from left to right.
• For the 4-th query, take out the 3 leftmost balls contained in the cylinder.
  The numbers written on the balls taken out are 2,3,3, for a sum of 8, which should be printed. The cylinder has now balls with numbers (3,3) written on them, from left to right.

Sample Input 2

2
1 1000000000 1000000000
2 1000000000

Sample Output 2

1000000000000000000

Sample Input 3

5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

Sample Output 3

There may be nothing you should print.

Problem Statement

There is a simple undirected graph with N vertices numbered 1 through N and M edges numbered 1 through M. Edge i connects vertex u_i and vertex v_i.
Every vertex is painted either red or blue. The color of vertex i is represented by C_i; vertex i is painted red if C_i is 0 and blue if C_i is 1.

Now, Takahashi is on vertex 1 and Aoki is on vertex N.
They may repeat the following move zero or more times.

• Each of the two simultaneously moves to a vertex adjacent to the current vertex.
  Here, the vertices that Takahashi and Aoki move to must have different colors.

By repeating the move above, can Takahashi and Aoki simultaneously end up on vertices N and 1, respectively?
If it is possible, find the minimum number of moves required. If it is impossible, print -1.

You are given T at the beginning of the input. Solve the problem for T test cases.

Constraints

• 1 \leq T \leq 1000
• 2 \leq N \leq 2000
• 1 \leq M \leq \min(\frac{N(N-1)}{2}, 2000)
• C_i \in \lbrace 0, 1 \rbrace
• 1 \leq u_i, v_i \leq N
• The graph given in the input is simple.
• All values in the input are integers.
• The sum of N over all test cases does not exceed 2000.
• The sum of M over all test cases does not exceed 2000.

Sample Input 1

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

Sample Output 1

3
-1
3

For the 1-st test case, Takahashi and Aoki can achieve the objective by making the following 3 moves, which is the minimum number:

• Takahashi moves to vertex 3, and Aoki moves to vertex 2.
• Takahashi moves to vertex 2, and Aoki moves to vertex 3.
• Takahashi moves to vertex 4, and Aoki moves to vertex 1.

Note that in the 1-st move, it is disallowed that both Takahashi and Aoki move to vertex 2 (because the colors of vertices that Takahashi and Aoki move to must be different.)

For the 2-nd case, no matter how they move, they cannot achieve the objective.

Problem Statement

There are N sequences of length M, denoted as A_1, A_2, \ldots, A_N. The i-th sequence is represented by M integers A_{i,1}, A_{i,2}, \ldots, A_{i,M}.

Two sequences X and Y of length M are said to be similar if and only if the number of indices i (1 \leq i \leq M) such that X_i = Y_i is odd.

Find the number of pairs of integers (i,j) satisfying 1 \leq i < j \leq N such that A_i and A_j are similar.

Constraints

• 1 \leq N \leq 2000
• 1 \leq M \leq 2000
• 1 \leq A_{i,j} \leq 999
• All input values are integers.

Sample Input 1

3 3
1 2 3
1 3 4
2 3 4

Sample Output 1

1

The pair (i,j) = (1,2) satisfies the condition because there is only one index k such that A_{1,k} = A_{2,k}, which is k=1.

The pairs (i,j) = (1,3), (2,3) do not satisfy the condition, making (1,2) the only pair that does.

Sample Input 2

6 5
8 27 27 10 24
27 8 2 4 5
15 27 26 17 24
27 27 27 27 27
27 7 22 11 27
19 27 27 27 27

Sample Output 2

5