Problem Statement

You are given an integer N. If N is between -2^{31} and 2^{31}-1 (inclusive), print Yes; otherwise, print No.

Constraints

• -2^{63} \leq N < 2^{63}
• N is an integer.

Sample Input 1

10

Sample Output 1

Yes

10 is between -2^{31} and 2^{31}-1, so Yes should be printed.

Sample Input 2

-9876543210

Sample Output 2

No

-9876543210 is less than -2^{31}, so No should be printed.

Sample Input 3

483597848400000

Sample Output 3

No

483597848400000 is greater than 2^{31}-1, so No should be printed.

Problem Statement

You are given a string S, which represents a weather forecast for the seven days starting tomorrow.
The i-th of those seven days is forecast to be sunny if the i-th character of S is o, and rainy if that character is x.

Tell us whether the N-th day is forecast to be sunny.

Constraints

• N is an integer between 1 and 7 (inclusive).
• S is a string of length 7 consisting of o and x.

Sample Input 1

4
oooxoox

Sample Output 1

No

The forecast for each of the seven days starting tomorrow is as follows: sunny, sunny, sunny, rainy, sunny, sunny, rainy.
In particular, the fourth day is forecast to be rainy.

Sample Input 2

7
ooooooo

Sample Output 2

Yes

Problem Statement

You are given N-by-N matrices A and B where each element is 0 or 1.
Let A_{i,j} and B_{i,j} denote the element at the i-th row and j-th column of A and B, respectively.
Determine whether it is possible to rotate A so that B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1.
Here, to rotate A is to perform the following operation zero or more times:

• for every pair of integers (i, j) such that 1 \leq i, j \leq N, simultaneously replace A_{i,j} with A_{N + 1 - j,i}.

Constraints

• 1 \leq N \leq 100
• Each element of A and B is 0 or 1.
• All values in the input are integers.

Sample Input 1

3
0 1 1
1 0 0
0 1 0
1 1 0
0 0 1
1 1 1

Sample Output 1

Yes

Initially, A is :

0 1 1
1 0 0
0 1 0

After performing the operation once, A is :

0 1 0
1 0 1 
0 0 1

After performing the operation once again, A is :

0 1 0
0 0 1
1 1 0

Here, B_{i,j} = 1 for every pair of integers (i, j) such that A_{i,j} = 1, so you should print Yes.

Sample Input 2

2
0 0
0 0
1 1
1 1

Sample Output 2

Yes

Sample Input 3

5
0 0 1 1 0
1 0 0 1 0
0 0 1 0 1
0 1 0 1 0
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0
0 0 1 1 1
1 0 1 0 1
1 1 0 1 0

Sample Output 3

No

Problem Statement

Takahashi ate N plates of sushi at a sushi restaurant. The color of the i-th plate is represented by a string C_i.

The price of a sushi corresponds to the color of the plate. For each i=1,\ldots,M, the sushi on a plate whose color is represented by a string D_i is worth P_i yen a plate (yen is the currency of Japan). If the color does not coincide with any of D_1,\ldots, and D_M, it is worth P_0 yen a plate.

Find the total amount of the prices of sushi that Takahashi ate.

Constraints

• 1\leq N,M\leq 100
• C_i and D_i are strings of length between 1 and 20, inclusive, consisting of lowercase English letters.
• D_1,\ldots, and D_M are distinct.
• 1\leq P_i\leq 10000
• N, M, and P_i are integers.

Sample Input 1

3 2
red green blue
blue red
800 1600 2800

Sample Output 1

5200

A blue plate, red plate, and green plate are worth P_1 = 1600, P_2 = 2800, and P_0 = 800 yen, respectively.

The total amount of the prices of the sushi that he ate is 2800+800+1600=5200 yen.

Sample Input 2

3 2
code queen atcoder
king queen
10 1 1

Sample Output 2

21

Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

1. Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of S:

   • (x+1,y) if S_i is R;
   • (x-1,y) if S_i is L;
   • (x,y+1) if S_i is U;
   • (x,y-1) if S_i is D.

2. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

• 1\leq N,M,H,K\leq 2\times 10^5
• S is a string of length N consisting of R, L, U, and D.
• |x_i|,|y_i| \leq 2\times 10^5
• (x_i, y_i) are pairwise distinct.
• All values in the input are integers, except for S.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

• 1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.

• 2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.

• 3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.

• 4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

• 1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.

• 2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.

Problem Statement

Person 0, Person 1, \ldots, and Person (N-1) are sitting around a turntable in their counterclockwise order, evenly spaced. Dish p_i is in front of Person i on the table.
You may perform the following operation 0 or more times:

• Rotate the turntable by one N-th of a counterclockwise turn. As a result, the dish that was in front of Person i right before the rotation is now in front of Person (i+1) \bmod N.

When you are finished, Person i is happy if Dish i is in front of Person (i-1) \bmod N, Person i, or Person (i+1) \bmod N.
Find the maximum possible number of happy people.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 0 \leq p_i \leq N-1
• p_i \neq p_j if i \neq j.
• All values in input are integers.

Sample Input 1

4
1 2 0 3

Sample Output 1

4

The figure below shows the table after one operation.

Here, there are four happy people:

• Person 0 is happy because Dish 0 is in front of Person 3\ (=(0-1) \bmod 4);
• Person 1 is happy because Dish 1 is in front of Person 1\ (=1);
• Person 2 is happy because Dish 2 is in front of Person 2\ (=2);
• Person 3 is happy because Dish 3 is in front of Person 0\ (=(3+1) \bmod 4).

There cannot be five or more happy people, so the answer is 4.

Sample Input 2

3
0 1 2

Sample Output 2

3

Sample Input 3

10
3 9 6 1 7 2 8 0 5 4

Sample Output 3

5

Problem Statement

There are N squares indexed 0 through (N-1) arranged in a line. Snuke is going to mark every square by the following procedure.

1. Mark square 0.
2. Repeat the following steps i - iii (N-1) times.
   1. Initialize a variable x with (A+D) \bmod N, where A is the index of the square marked last time.
   2. While square x is marked, repeat replacing x with (x+1) \bmod N.
   3. Mark square x.

Find the index of the square that Snuke marks for the K-th time.

Given T test cases, find the answer for each of them.

Constraints

• 1\leq T \leq 10^5
• 1\leq K\leq N \leq 10^9
• 1\leq D \leq 10^9
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

0
2
1
3
0
3
1
4
2

If N=4 and D=2, Snuke marks the squares as follows.

1. Mark square 0.
2. (1-st iteration) Let x=(0+2)\bmod 4=2. Since square 2 is not marked, mark it.
   (2-nd iteration) Let x=(2+2)\bmod 4=0. Since square 0 is marked, let x=(0+1)\bmod 4=1. Since square 1 is not marked, mark it.
   (3-rd iteration) Let x=(1+2)\bmod 4=3. Since square 3 is not marked, mark it.

Problem Statement

We have a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

Each square contains an integer. For each i = 1, 2, \ldots, N, the square (r_i, c_i) contains a positive integer a_i. The other square contains a 0.

Initially, there is a piece on the square (R, C). Takahashi can move the piece to a square other than the square it occupies now, any number of times. However, when moving the piece, both of the following conditions must be satisfied.

• The integer written on the square to which the piece is moved is strictly greater than the integer written on the square from which the piece is moved.
• The squares to and from which the piece is moved are in the same row or the same column.

For each i = 1, 2, \ldots, N, print the maximum number of times Takahashi can move the piece when (R, C) = (r_i, c_i).

Constraints

• 2 \leq H, W \leq 2 \times 10^5
• 1 \leq N \leq \min(2 \times 10^5, HW)
• 1 \leq r_i \leq H
• 1 \leq c_i \leq W
• 1 \leq a_i \leq 10^9
• i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
0
2
0
3
1
0

The grid contains the following integers.

4 7 0
3 0 5
2 5 5

• When (R, C) = (r_1, c_1) = (1, 1), you can move the piece once by moving it as (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_2, c_2) = (1, 2), you cannot move the piece at all.
• When (R, C) = (r_3, c_3) = (2, 1), you can move the piece twice by moving it as (2, 1) \rightarrow (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_4, c_4) = (2, 3), you cannot move the piece at all.
• When (R, C) = (r_5, c_5) = (3, 1), you can move the piece three times by moving it as (3, 1) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2).
• When (R, C) = (r_6, c_6) = (3, 2), you can move the piece once by moving it as (3, 2) \rightarrow (1, 2).
• When (R, C) = (r_7, c_7) = (3, 3), you cannot move the piece at all.

Sample Input 2

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

Sample Output 2

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

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
For each pair of integers (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, (i, j) contains a positive integer A_{i,j}. Additionally, every square is painted white.

Takahashi has a rectangular black stamp that can cover h_1 rows and w_1 columns, and Aoki has a rectangular white stamp that can cover h_2 rows and w_2 columns. Using these stamps and the grid, they will play a game against each other.

First, Takahashi presses his black stamp to paint a rectangular region with h_1 rows and w_1 columns black.
That is, he chooses a pair of integers (i, j) such that 1 \leq i \leq H - h_1 + 1 and 1 \leq j \leq W - w_1 + 1, and paints black every square (r, c) such that i \leq r \leq i + h_1 - 1 and j \leq c \leq j + w_1 - 1.

Second, Aoki presses his white stamp to paint a rectangular region with h_2 rows and w_2 columns white.
That is, he chooses a pair of integers (i, j) such that 1 \leq i \leq H - h_2 + 1 and 1 \leq j \leq W - w_2 + 1, and paints white every square (r, c) such that i \leq r \leq i + h_2 - 1 and j \leq c \leq j + w_2 - 1.
If some of these squares are already painted black by Takahashi, they will also become white.

The game's score is defined as the sum of the integers written on the squares painted black after Takahashi and Aoki press their stamps as described above. Takahashi follows the optimal strategy to make the score as large as possible, while Aoki follows the optimal strategy to make the score as small as possible. What will the game's score be?

Constraints

• 2 \leq H, W \leq 1000
• 1 \leq h_1, h_2 \leq H
• 1 \leq w_1, w_2 \leq W
• 1 \leq A_{i, j} \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

19

The game will go as follows.

• Initially, all squares are painted white.
• First, Takahashi presses his 2 \times 3 black stamp to paint the following six squares black: (2, 2), (2, 3), (2 ,4), (3, 2), (3, 3), (3, 4).
• Second, Aoki presses his 3 \times 1 white stamp to paint the following three squares white: (1, 4), (2, 4), (3, 4).
• Eventually, the following four squares are painted black: (2, 2), (2, 3), (3, 2), (3, 3), for a score of 9 + 2 + 3 + 5 = 19.

Sample Input 2

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

Sample Output 2

0

After Aoki presses his stamp, all squares will be white, for a score of 0.

Sample Input 3

10 10 3 7 2 3
9 7 19 7 10 4 13 9 4 8
10 15 16 3 18 19 17 12 13 2
12 18 4 9 13 13 6 13 5 2
16 12 2 14 18 17 14 7 8 12
12 13 17 12 14 15 19 7 13 15
5 2 16 10 4 6 1 2 7 8
10 14 14 10 9 13 11 4 9 19
16 12 3 19 19 6 2 19 14 20
15 3 19 19 2 10 1 4 3 15
13 20 5 6 19 1 7 17 10 19

Sample Output 3

180