Problem Statement

There are N snakes.

Initially, the thickness of the i-th snake is T_i, and its length is L_i.

The weight of a snake is defined as the product of its thickness and length.

For each integer k satisfying 1 \leq k \leq D, find the weight of the heaviest snake when every snake's length has increased by k.

Constraints

• 1 \leq N, D \leq 100
• 1 \leq T_i, L_i \leq 100
• All input values are integers.

Sample Input 1

4 3
3 3
5 1
2 4
1 10

Sample Output 1

12
15
20

When every snake’s length has increased by 1, the snakes' weights become 12, 10, 10, 11, so print 12 on the first line.

When every snake’s length has increased by 2, the snakes' weights become 15, 15, 12, 12, so print 15 on the second line.

When every snake’s length has increased by 3, the snakes' weights become 18, 20, 14, 13, so print 20 on the third line.

Sample Input 2

1 4
100 100

Sample Output 2

10100
10200
10300
10400

Problem Statement

Note: This problem has almost the same setting as Problem F. Only the parts in bold in the main text and constraints differ.

You are holding a ring with both hands. This ring consists of N\ (N \geq 3) parts numbered 1,2,\dots,N, where parts i and i+1 (1 \leq i \leq N-1) are adjacent, and parts 1 and N are also adjacent.

Initially, your left hand is holding part 1, and your right hand is holding part 2. In one operation, you can do the following:

• Move one of your hands to an adjacent part of the part it is currently holding. However, you can do this only if the other hand is not on the destination part.

The following figure shows the initial state and examples of operations that can and cannot be made from there. The number written on each part of the ring represents the part number, and the circles labeled L and R represent your left and right hands, respectively.

You need to follow Q instructions given to you in order. The i-th (1 \leq i \leq Q) instruction is represented by a character H_i and an integer T_i, meaning the following:

• Perform some number of operations (possibly zero) so that your left hand (if H_i is L) or your right hand (if H_i is R) is holding part T_i. Here, you must not move the other hand not specified by H_i.

It is guaranteed that only achievable instructions are given.

Find the minimum total number of operations required to follow all the instructions.

Constraints

• 3 \leq N \leq 100
• 1 \leq Q \leq 100
• H_i is L or R.
• 1 \leq T_i \leq N
• N, Q, and T_i are integers.
• Only achievable instructions are given (see the problem statement for details).

Sample Input 1

6 3
R 4
L 5
R 6

Sample Output 1

8

By performing the following operations, you can follow all Q instructions in order.

1. Move your right hand as part 2 \rightarrow 3 \rightarrow 4 to follow the first instruction.
2. Move your left hand as part 1 \rightarrow 6 \rightarrow 5 to follow the second instruction.
3. Move your right hand as part 4 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 6 to follow the third instruction.

In this case, the total number of operations is 2+2+4=8, which is the minimum. (Note that when following the third instruction, you cannot move your right hand as part 4 \rightarrow 5 \rightarrow 6.)

Sample Input 2

100 2
L 1
R 2

Sample Output 2

0

There are cases where you can follow the instructions without performing any operations.

Sample Input 3

30 8
R 23
R 26
R 29
L 20
R 29
R 19
L 7
L 16

Sample Output 3

92

Problem Statement

There is a single integer N written on a blackboard.
Takahashi will repeat the following series of operations until all integers not less than 2 are removed from the blackboard:

• Choose one integer x not less than 2 written on the blackboard.
• Erase one occurrence of x from the blackboard. Then, write two new integers \left \lfloor \dfrac{x}{2} \right\rfloor and \left\lceil \dfrac{x}{2} \right\rceil on the blackboard.
• Takahashi must pay x yen to perform this series of operations.

Here, \lfloor a \rfloor denotes the largest integer not greater than a, and \lceil a \rceil denotes the smallest integer not less than a.

What is the total amount of money Takahashi will have paid when no more operations can be performed?
It can be proved that the total amount he will pay is constant regardless of the order in which the operations are performed.

Constraints

• 2 \leq N \leq 10^{17}

Sample Input 1

3

Sample Output 1

5

Here is an example of how Takahashi performs the operations:

• Initially, there is one 3 written on the blackboard.
• He chooses 3. He pays 3 yen, erases one 3 from the blackboard, and writes \left \lfloor \dfrac{3}{2} \right\rfloor = 1 and \left\lceil \dfrac{3}{2} \right\rceil = 2 on the blackboard.
• There is one 2 and one 1 written on the blackboard.
• He chooses 2. He pays 2 yen, erases one 2 from the blackboard, and writes \left \lfloor \dfrac{2}{2} \right\rfloor = 1 and \left\lceil \dfrac{2}{2} \right\rceil = 1 on the blackboard.
• There are three 1s written on the blackboard.
• Since all integers not less than 2 have been removed from the blackboard, the process is finished.

Takahashi has paid a total of 3 + 2 = 5 yen for the entire process, so print 5.

Sample Input 2

340

Sample Output 2

2888

Sample Input 3

100000000000000000

Sample Output 3

5655884811924144128

Problem Statement

There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).

Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.

Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.

After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.

Constraints

• 1 \leq N, D \leq 2000
• -1000 \leq X_i, Y_i \leq 1000
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All input values are integers.

Sample Input 1

4 5
2 -1
3 1
8 8
0 5

Sample Output 1

Yes
Yes
No
Yes

The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.

Sample Input 2

3 1
0 0
-1000 -1000
1000 1000

Sample Output 2

Yes
No
No

Sample Input 3

9 4
3 2
6 -1
1 6
6 5
-2 -3
5 3
2 -3
2 1
2 6

Sample Output 3

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No

Problem Statement

There is an N \times N grid. Takahashi wants to color each cell black or white so that all of the following conditions are satisfied:

• For every row, the following condition holds:
• There exists an integer i\ (0\leq i\leq N) such that the leftmost i cells are colored black, and the rest are colored white.
• For every column, the following condition holds:
• There exists an integer i\ (0\leq i\leq N) such that the topmost i cells are colored black, and the rest are colored white.

Out of these N^2 cells, M of them have already been colored. Among them, the i-th one is at the X_i-th row from the top and the Y_i-th column from the left, and it is colored black if C_i is B and white if C_i is W.

Determine whether he can color the remaining uncolored N^2 - M cells so that all the conditions are satisfied.

Constraints

• 1\leq N\leq 10^9
• 1\leq M\leq \min(N^2,2\times 10^5)
• 1\leq X_i,Y_i\leq N
• (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
• C_i is B or W.
• All input numbers are integers.

Sample Input 1

4 3
4 1 B
3 2 W
1 3 B

Sample Output 1

Yes

For example, one can color the grid as in the following figure to satisfy the conditions. The cells already colored are surrounded by red borders.

Sample Input 2

2 2
1 2 W
2 2 B

Sample Output 2

No

No matter how the remaining two cells are colored, the conditions cannot be satisfied.

Sample Input 3

1 1
1 1 W

Sample Output 3

Yes

Sample Input 4

2289 10
1700 1083 W
528 967 B
1789 211 W
518 1708 W
1036 779 B
136 657 B
759 1497 B
902 1309 B
1814 712 B
936 763 B

Sample Output 4

No