Problem Statement

You are playing the slots.

The result of a spin is represented by three uppercase English letters C_1, C_2, and C_3. It is considered a win when all of them are the same letter.

Determine whether it is a win.

Constraints

• C_i is an uppercase English letter.

Sample Input 1

SSS

Sample Output 1

Won

All of them are the same letter, so it is a win.

Sample Input 2

WVW

Sample Output 2

Lost

It is not a win.

Problem Statement

Takahashi had N glasses of liquor.

The amount and alcohol percentage of the i-th liquor were V_i milliliters and P_i percent by volume, respectively.

Takahashi gets drunk when his alcohol intake exceeds X milliliters.

Which of the N liquors was he drinking when he gets drunk? If he was not drunk even after drinking all the liquors, print -1 instead.

Constraints

• All values in input are integers.
• 1 \leq N \leq 10^3
• 0 \leq X \leq 10^6
• 1 \leq V_i \leq 10^3
• 0 \leq P_i \leq 100

Sample Input 1

2 15
200 5
350 3

Sample Output 1

2

The 1-st liquor contains 200\times \dfrac{5}{100}=10 milliliters of alcohol.

The 2-nd liquor contains 350\times \dfrac{3}{100}=10.5 milliliters of alcohol.

His alcohol intake exceeds 15 milliliters for the first time when drinking the 2-nd liquor.

Sample Input 2

2 10
200 5
350 3

Sample Output 2

2

When his alcohol intake is exactly X milliliters, he is still not drunk.

Sample Input 3

3 1000000
1000 100
1000 100
1000 100

Sample Output 3

-1

He seems to be immune to alcohol.

Problem Statement

There are N dishes arranged in a row in front of Takahashi. The i-th dish from the left has A_i oranges on it.

Takahashi will choose a triple of integers (l, r, x) satisfying all of the following conditions:

• 1\leq l \leq r \leq N;
• 1 \le x;
• for every integer i between l and r (inclusive), x \le A_i.

He will then pick up and eat x oranges from each of the l-th through r-th dishes from the left.

At most how many oranges can he eat by choosing the triple (l, r, x) to maximize this number?

Constraints

• All values in input are integers.
• 1 \leq N \leq 10^4
• 1 \leq A_i \leq 10^5

Sample Input 1

6
2 4 4 9 4 9

Sample Output 1

20

By choosing (l,r,x)=(2,6,4), he can eat 20 oranges.

Sample Input 2

6
200 4 4 9 4 9

Sample Output 2

200

By choosing (l,r,x)=(1,1,200), he can eat 200 oranges.

Problem Statement

Given are N strings S_1,\ldots,S_N, each of which is AND or OR.

Find the number of tuples of N+1 variables (x_0,\ldots,x_N), where each element is \text{True} or \text{False}, such that the following computation results in y_N being \text{True}:

• y_0=x_0;
• for i\geq 1, y_i=y_{i-1} \land x_i if S_i is AND, and y_i=y_{i-1} \lor x_i if S_i is OR.

Here, a \land b and a \lor b are logical operators.

Constraints

• 1 \leq N \leq 60
• S_i is AND or OR.

Sample Input 1

2
AND
OR

Sample Output 1

5

For example, if (x_0,x_1,x_2)=(\text{True},\text{False},\text{True}), we have y_2 = \text{True}, as follows:

• y_0=x_0=\text{True}
• y_1=y_0 \land x_1 = \text{True} \land \text{False}=\text{False}
• y_2=y_1 \lor x_2 = \text{False} \lor \text{True}=\text{True}

All of the five tuples (x_0,x_1,x_2) resulting in y_2 = \text{True} are shown below:

• (\text{True},\text{True},\text{True})
• (\text{True},\text{True},\text{False})
• (\text{True},\text{False},\text{True})
• (\text{False},\text{True},\text{True})
• (\text{False},\text{False},\text{True})

Sample Input 2

5
OR
OR
OR
OR
OR

Sample Output 2

63

All tuples except the one filled entirely with \text{False} result in y_5 = \text{True}.

Problem Statement

There are N pieces on a two-dimensional plane. The coordinates of Piece i are (X_i,Y_i). There may be multiple pieces at the same coordinates.

We will do M operations \mathrm{op}_1, \ldots, \mathrm{op}_M, one by one. There are four kinds of operations, described below along with their formats in input.

• 1：Rotate every piece 90 degrees clockwise about the origin;
• 2：Rotate every piece 90 degrees counterclockwise about the origin;
• 3 p：Move each piece to the point symmetric to it about the line x=p;
• 4 p：Move each piece to the point symmetric to it about the line y=p.

You are given Q queries. In the i-th query, given two integers A_i and B_i, print the coordinates of Piece B_i just after the A_i-th operation. Here, the moment just before the 1-st operation is considered to be the moment just after "the 0-th operation".

Constraints

• All values in input are integers.
• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1 \leq Q \leq 2\times 10^5
• -10^9 \leq X_i,Y_i \leq 10^9
• \mathrm{op}_i is in the format of one of the four kinds of operations.
• In an operation with the form 3 p or 4 p, -10^9 \leq p \leq 10^9.
• 0 \leq A_i \leq M
• 1 \leq B_i \leq N

Sample Input 1

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

Sample Output 1

1 2
2 -1
4 -1
1 4
1 0

Initially, the only piece - Piece 1 - is at (1, 2). Each operation moves the piece as follows: (1,2)\to(2,-1)\to(4,-1)\to(1,4)\to(1,0).

Sample Input 2

2
1000000000 0
0 1000000000
4
3 -1000000000
4 -1000000000
3 1000000000
4 1000000000
2
4 1
4 2

Sample Output 2

5000000000 4000000000
4000000000 5000000000

Problem Statement

Takahashi is playing sugoroku.

The board has N+1 squares numbered 0 to N. Takahashi starts at Square 0 and head to Square N.

In this sugoroku, we use a wheel showing numbers from 1 through M with equal probability. In each turn, Takahashi spins the wheel and advances by the number shown by the wheel. When it makes him reach Square N or go past it, he wins.

Some of the squares send him to Square 0 when he stops on them. There are K such squares: Square A_1, \ldots, A_K.

Find the expected value of the number of times Takahashi spins the wheel before he wins. If it is impossible to win, print -1 instead.

Constraints

• All values in input are integers.
• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 0 \leq K \leq 10
• 0 < A_1 < \ldots < A_K < N

Sample Input 1

2 2 0

Sample Output 1

1.5000

If the wheel shows 1 in the first spin, he will need two spins to win; if the wheel shows 2 in the first spin, he will need one spin to win. Thus, the expected number of spins is 1.5.

Sample Input 2

2 2 1
1

Sample Output 2

2.0000

If the wheel shows 1, he advances to Square 1, but it sends him back to Square 0.
Thus, he keeps spinning the wheel until he gets 2 and wins.
The probability that he gets 2 for the first time in the i-th spin is \frac{1}{2^i}, so the expected number of spins is \sum_{i = 1}^{\infty} (i \times \frac{1}{2^i}) = 2.

Sample Input 3

100 6 10
11 12 13 14 15 16 17 18 19 20

Sample Output 3

-1

Sample Input 4

100000 2 2
2997 92458

Sample Output 4

201932.2222