Problem Statement

You are given positive integers N and M.
Print N lines.
The i-th line (1\leq i\leq N) should contain OK if i\leq M, and Too Many Requests otherwise.

Constraints

• 1 \leq N \leq 10
• 1 \leq M \leq 10
• N and M are integers.

Sample Input 1

5 3

Sample Output 1

OK
OK
OK
Too Many Requests
Too Many Requests

Since N=5 and M=3,
print OK on the 1st, 2nd, and 3rd lines,
and print Too Many Requests on the 4th and 5th lines.

Sample Input 2

3 5

Sample Output 2

OK
OK
OK

Since N=3 and M=5, print OK on the 1st, 2nd, and 3rd lines.

Problem Statement

You are given an integer sequence of length N, A=(A_1,A_2,\ldots,A_N), and an integer M.

Determine whether it is possible to remove one of the N elements of A so that the sum of the remaining (N-1) elements is exactly M.

Constraints

• 2\le N\le 100
• 0\le M\le 10000
• 0\le A_i\le 100
• All input values are integers.

Sample Input 1

4 10
3 2 3 4

Sample Output 1

Yes

If you choose A_1,A_3,A_4, the sum is 3+3+4=10. Therefore, print Yes.

Sample Input 2

5 16
3 3 4 2 5

Sample Output 2

No

No matter how you choose four elements, their sum is not equal to 16. Therefore, print No.

Sample Input 3

6 16
0 8 0 2 6 8

Sample Output 3

Yes

Problem Statement

You are given an integer sequence of length N, A=(A_1,A_2,\ldots,A_N).
Find the number of triples of integers (i,j,k) satisfying 1\leq i<j<k\leq N that satisfy the following condition:

Exactly two distinct values are contained in A_i,A_j,A_k. That is, two of A_i,A_j,A_k are equal, and the remaining one is different.

Constraints

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

Sample Input 1

5
3 2 5 2 2

Sample Output 1

6

For example, (i,j,k)=(1,2,4) satisfies the condition because exactly two distinct values, 2 and 3, are contained in A_1=3, A_2=2, and A_4=2.
Including this, the six triples (i,j,k)=(1,2,4),(1,2,5),(1,4,5),(2,3,4),(2,3,5),(3,4,5) satisfy the condition.
Therefore, print 6.

Sample Input 2

3
1 1 1

Sample Output 2

0

There may be no triples that satisfy the condition.

Problem Statement

There is a pond with a circumference of M, and on its shore stand one hut and N people.
For a real number x (0\leq x <M), define point x as the location that is x distance clockwise from the hut.
The i-th person is at point A_i. Multiple people may be standing at the same location.

Additionally, an integer C not greater than N is given. For i=0,1,\ldots,M-1, define X_i as follows:

1. Takahashi starts at point (i+0.5) and begins moving clockwise.
2. Takahashi continues moving (clockwise) as long as the total number of people he has met is less than C, and stops when it becomes C or more. Here, "meeting a person at point y" means that Takahashi reaches point y.
3. Let X_i be the number of people Takahashi met before stopping. Here, if there are multiple people at the point where Takahashi stopped, all the people there are counted as people he met, and particularly, X_i may be greater than C.

Find the sum of X_i over i=0,1,\ldots,M-1, that is, \displaystyle\sum_{i=0}^{M-1} X_i.

Constraints

• 1\leq N\leq 5\times 10^5
• 1\leq M\leq 10^{12}
• 0\leq A_i\leq M-1
• 1\leq C\leq N
• All input values are integers.

Sample Input 1

5 3 2
1 2 1 0 1

Sample Output 1

9

When i=0, Takahashi starts at point 0.5 and moves clockwise. Then, the following happens:

• At point 1, he meets the 1st, 3rd, and 5th people, a total of three people, and the total number of people met so far is 3. This is not less than C=2, so Takahashi stops there. Therefore, X_0=3.

When i=1, Takahashi starts at point 1.5 and moves clockwise. Then, the following happens:

• At point 2, he meets the 2nd person. The total number of people met so far is 1, so he continues moving.
• At point 0, he meets the 4th person, and the total number of people met so far is 2. This is not less than C=2, so Takahashi stops there. Therefore, X_1=2.

When i=2, Takahashi starts at point 2.5 and moves clockwise. Then, the following happens:

• At point 0, he meets the 4th person. The total number of people met so far is 1, so he continues moving.
• At point 1, he meets the 1st, 3rd, and 5th people, a total of three people, and the total number of people met so far is 4. This is not less than C=2, so Takahashi stops there. Therefore, X_2=4.

Therefore, the answer is X_0+X_1+X_2=3+2+4=9.

Sample Input 2

1 1000000000000 1
1

Sample Output 2

1000000000000

Regardless of the starting position, Takahashi stops when he meets the only person standing around the pond, who is at point 1.
Therefore, X_i=1 regardless of i, and the answer is 10^{12}.

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices and edges of G are numbered as vertices 1,2,\ldots,N and edges 1,2,\ldots,M, respectively, and edge i connects vertices U_i and V_i.
You can move bidirectionally between vertices connected by an edge in time 1.

Additionally, each vertex is either safe or dangerous, and this state is given by a string S of length N consisting of S and D.
Specifically, vertex i is safe when the i-th character (1\leq i\leq N) of S is S, and vertex i is dangerous when it is D.
It is guaranteed that there are at least two safe vertices and at least one dangerous vertex.

For each dangerous vertex v, find the following value:

The minimum possible time to start from some safe vertex, pass through v, and move to a safe vertex different from the starting vertex.

Constraints

• 3\leq N\leq 2\times 10^5
• N-1\leq M\leq 2\times 10^5
• 1\leq U_i,V_i\leq N
• U_i\neq V_i
• If i\neq j, then \{ U_i,V_i \}\neq \{ U_j,V_j \}.
• S is a string of length N consisting of S and D.
• N,M,U_i,V_i are all integers.
• G is connected.
• There are at least two safe vertices.
• There is at least one dangerous vertex.

Sample Input 1

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

Sample Output 1

2
3

The dangerous vertices are (in ascending order of vertex number) vertices 3 and 4.

For vertex 3, moving from vertex 1 \to vertex 3 \to vertex 2 (for example) satisfies the condition.
The time required for this movement is 2, and this is the minimum.
Therefore, print 2 on the 1st line.

For vertex 4, moving from vertex 1 \to vertex 3 \to vertex 4 \to vertex 5 (for example) satisfies the condition.
The time required for this movement is 3, and there is no way to move that satisfies the condition with time 2 or less, so this is the minimum.
Therefore, print 3 on the 2nd line.

Sample Input 2

3 2
1 2
2 3
SSD

Sample Output 2

3

The dangerous vertex is vertex 3.

Moving from vertex 1 \to vertex 2 \to vertex 3 \to vertex 2 (for example) satisfies the condition.
The time required for this movement is 3, and this is the minimum.
Note that movements such as vertex 2 \to vertex 3 \to vertex 2 do not satisfy the condition that the destination is "different from the starting vertex".

Problem Statement

You are given a grid with three rows and N columns. Denote the cell at the i-th row from the top and j-th column from the left as cell (i,j). Cell (i,j) is a wall cell if S_{i,j} is #, and an empty cell and passable if it is ..

You are given Q queries, which you should process in order.

Each query gives integers r and c, and you should flip the state of cell (r,c). That is, if cell (r,c) is a wall cell, make it an empty cell, and if it is an empty cell, make it a wall cell. Then, output the answer to the following problem:

Consider moving from cell (1,1) to cell (3,N) by repeatedly moving to an empty cell adjacent up, down, left, or right. Determine whether cell (3,N) is reachable, and if reachable, find the minimum number of moves.

Constraints

• 2\le N\le 2\times 10^5
• S_{i,j} is # or ..
• S_{1,1}=S_{3,N}= .
• 1\le Q\le 2\times 10^5
• 1\le r\le 3
• 1\le c\le N
• (r,c) \neq (1,1),(3,N)
• N,Q,r,c are integers.

Sample Input 1

5
.#...
.#.#.
...#.
3
1 2
1 2
2 3

Sample Output 1

6
10
-1

In the first query, flip the state of cell (1,2). As a result, the state of each cell becomes:

.....
.#.#.
...#.

At this time, by moving from cell (1,1) through cells (1,2),(1,3),(1,4),(1,5),(2,5),(3,5) in order, you can reach cell (3,5) in six moves.

In the second query, flip the state of cell (1,2). As a result, the state of each cell becomes:

.#...
.#.#.
...#.

At this time, by moving from cell (1,1) through cells (2,1),(3,1),(3,2),(3,3),(2,3),(1,3),(1,4),(1,5),(2,5),(3,5) in order, you can reach cell (3,5) in ten moves.

In the third query, flip the state of cell (2,3). As a result, the state of each cell becomes:

.#...
.###.
...#.

At this time, no matter how you move, you cannot reach cell (3,5) from cell (1,1).

Sample Input 2

7
.#.....
.#..#..
...#...
6
2 5
3 4
3 5
2 5
1 4
1 4

Sample Output 2

10
8
10
12
-1
12

Problem Statement

You are given integers N,M,A,B,X,R.

Find the remainder when \displaystyle \sum_{k=0}^{N-1} X^{(Ak+B) \bmod M} is divided by R.

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

Constraints

• 1\le T\le 100
• 1\le N,M,R\le 10^9
• 0\le A,B < M
• 1\le X < R
• All input values are integers.

Sample Input 1

3
4 5 2 1 2 1000000000
777 429 33 58 1 1000000000
20251025 429429 777 1025 575757 998244353

Sample Output 1

15
777
445271630

Consider the first test case.

• When k=0: \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 0+1) \bmod 5}=2^1=2.
• When k=1: \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 1+1) \bmod 5}=2^3=8.
• When k=2: \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 2+1) \bmod 5}=2^0=1.
• When k=3: \displaystyle X^{(Ak+B) \bmod M}=2^{(2\times 3+1) \bmod 5}=2^2=4.

From the above, the desired value is the remainder when 2+8+1+4 is divided by 1000000000, which is 15. Therefore, print 15 on the 1st line.