Problem Statement

Takahashi came to a store to buy a pen. Here, a red pen costs R yen, a green pen costs G yen, and a blue pen costs B yen.

Takahashi dislikes the color C. If C is Red, he cannot buy a red pen; if C is Green, he cannot buy a green pen; and if C is Blue, he cannot buy a blue pen.

Determine the minimum amount of money he needs to buy one pen.

Constraints

• 1\leq R,G,B\leq 100
• R, G, and B are integers.
• C is Red, Green, or Blue.

Sample Input 1

20 30 10
Blue

Sample Output 1

20

A red pen costs 20 yen, a green pen costs 30 yen, and a blue pen costs 10 yen. Takahashi cannot buy a blue pen, but he can buy a red pen for 20 yen.

Sample Input 2

100 100 100
Red

Sample Output 2

100

Sample Input 3

37 39 93
Blue

Sample Output 3

37

Problem Statement

Takahashi's purse has one or more 100-yen coins in it and nothing else. (Yen is the Japanese currency.)

Is it possible that the total amount of money in the purse is X yen?

Constraints

• 0 \leq X \leq 1000
• All values in input are integers.

Sample Input 1

500

Sample Output 1

Yes

If the purse has five 100-yen coins, the total amount of money is 500 yen. Thus, it is possible that the total amount is X=500 yen, so we should print Yes.

Sample Input 2

40

Sample Output 2

No

Sample Input 3

0

Sample Output 3

No

Note that the purse has at least one 100-yen coin.

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Cell (i, j) is empty if C_{i, j} is ., and not empty if C_{i, j} is #.

Takahashi is currently at cell (S_i, S_j), and he will act according to the following rules for i = 1, 2, \ldots, |X| in order.

• If the i-th character of X is L, and the cell to the left of his current cell exists and is empty, he moves to the cell to the left. Otherwise, he stays in the current cell.
• If the i-th character of X is R, and the cell to the right of his current cell exists and is empty, he moves to the cell to the right. Otherwise, he stays in the current cell.
• If the i-th character of X is U, and the cell above his current cell exists and is empty, he moves to the cell above. Otherwise, he stays in the current cell.
• If the i-th character of X is D, and the cell below his current cell exists and is empty, he moves to the cell below. Otherwise, he stays in the current cell.

Print the cell where he is after completing the series of actions.

Constraints

• 1 \leq H, W \leq 50
• 1 \leq S_i \leq H
• 1 \leq S_j \leq W
• H, W, S_i, S_j are integers.
• C_{i, j} is . or #.
• C_{S_i, S_j} = .
• X is a string of length between 1 and 50, inclusive, consisting of L, R, U, D.

Sample Input 1

2 3
2 1
.#.
...
ULDRU

Sample Output 1

2 2

Takahashi starts at cell (2, 1). His series of actions are as follows:

• The 1st character of X is U, and the cell above (2, 1) exists and is an empty cell, so he moves to the cell above, which is (1, 1).
• The 2nd character of X is L, and the cell to the left of (1, 1) does not exist, so he stays at (1, 1).
• The 3rd character of X is D, and the cell below (1, 1) exists and is an empty cell, so he moves to the cell below, which is (2, 1).
• The 4th character of X is R, and the cell to the right of (2, 1) exists and is an empty cell, so he moves to the cell to the right, which is (2, 2).
• The 5th character of X is U, and the cell above (2, 2) exists but is not an empty cell, so he stays at (2, 2).

Therefore, after completing the series of actions, he is at cell (2, 2).

Sample Input 2

4 4
4 2
....
.#..
...#
....
DUUUURULRD

Sample Output 2

2 4

Sample Input 3

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

Sample Output 3

1 1

Problem Statement

N people participated in a programming contest consisting of M problems.
The participants are numbered person 1, person 2, \ldots, person N, and the problems are numbered problem 1, problem 2, \ldots, problem M.

In this contest, K events occurred in order; in the i-th event (1\leq i\leq K), the following happened:

• Person A_i solved problem B_i.

The same event does not occur two or more times. Also, apart from these K events, nobody solves any problem.

Output the numbers of all people who solved all problems.
If there are multiple such people, output them in ascending order of the time at which they solved all problems.

Constraints

• 1 \leq N \leq 10
• 1 \leq M \leq 10
• K \geq 1
• 1 \leq A_i \leq N
• 1 \leq B_i \leq M
• If i\neq j then (A_i,B_i)\neq (A_j,B_j).
• All input values are integers.

Sample Input 1

3 2 5
1 1
3 2
2 1
3 1
1 2

Sample Output 1

3 1

In the contest, the following happened in order.

• Person 1 solved problem 1. So far, person 1 has solved only problem 1.
• Person 3 solved problem 2. So far, person 3 has solved only problem 2.
• Person 2 solved problem 1. So far, person 2 has solved only problem 1.
• Person 3 solved problem 1. So far, person 3 has solved problems 1,2. Thus, at this point person 3 has solved all problems.
• Person 1 solved problem 2. So far, person 1 has solved problems 1,2. Thus, at this point person 1 has solved all problems.

Thus, the people who solved all problems are persons 1,3, and the one who solved all problems earlier is person 3. Thus, output 3,1 in this order, separated by spaces.

Sample Input 2

2 2 2
1 1
2 2

Sample Output 2

If there is no person who solved all problems, output nothing.

Problem Statement

You have N keys numbered 1, 2, \dots, N.
Some of these are real keys, while the others are dummies.

There is a door, Door X, into which you can insert any number of keys. Door X will open if and only if at least K real keys are inserted.

You have conducted M tests on these keys. The i-th test went as follows:

• You inserted C_i keys A_{i,1}, A_{i,2}, \dots, A_{i,C_i} into Door X.
• The test result is represented by a single English letter R_i.
  • R_i = o means that Door X opened in the i-th test.
  • R_i = x means that Door X did not open in the i-th test.

There are 2^N possible combinations of which keys are real and which are dummies. Among these, find the number of combinations that do not contradict any of the test results.
It is possible that the given test results are incorrect and no combination satisfies the conditions. In such a case, report 0.

Constraints

• N, M, K, C_i, and A_{i,j} are integers.
• 1 \le K \le N \le 15
• 1 \le M \le 100
• 1 \le C_i \le N
• 1 \le A_{i,j} \le N
• A_{i,j} \neq A_{i,k} if j \neq k.
• R_i is o or x.

Sample Input 1

3 2 2
3 1 2 3 o
2 2 3 x

Sample Output 1

2

In this input, there are three keys and two tests were conducted.
Two correct keys are required to open Door X.

• In the first test, keys 1, 2, 3 were used, and Door X opened.
• In the second test, keys 2, 3 were used, and Door X did not open.

There are two combinations of which keys are real and which are dummies that do not contradict any of the test results:

• Key 1 is real, key 2 is a dummy, and key 3 is real.
• Key 1 is real, key 2 is real, and key 3 is a dummy.

Sample Input 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

Sample Output 2

0

As mentioned in the problem statement, the answer may be 0.

Sample Input 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x

Sample Output 3

8

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

You are given an integer K greater than or equal to 2.
Find the minimum positive integer N such that N! is a multiple of K.

Here, N! denotes the factorial of N. Under the Constraints of this problem, we can prove that such an N always exists.

Constraints

• 2\leq K\leq 10^{12}
• K is an integer.

Sample Input 1

30

Sample Output 1

5

• 1!=1
• 2!=2\times 1=2
• 3!=3\times 2\times 1=6
• 4!=4\times 3\times 2\times 1=24
• 5!=5\times 4\times 3\times 2\times 1=120

Therefore, 5 is the minimum positive integer N such that N! is a multiple of 30. Thus, 5 should be printed.

Sample Input 2

123456789011

Sample Output 2

123456789011

Sample Input 3

280

Sample Output 3

7

Problem Statement

In the year 30XX, each submission to a certain contest requires a payment.

The contest has N problems. Problem i has S_i points, and each submission costs C_i yen.

When Takahashi submits to the i-th problem, he solves it with probability P_i %. Each submission’s outcome is independent of the others.

He has X yen. He cannot make any submission that would cause his total spending to exceed X yen.

Find the expected value of the total score of the problems he solves when he chooses submissions to maximize this value.

He may decide which problem to submit to next after seeing the result of the previous submission, and solving the same problem more than once awards the same score as solving it once.

Constraints

• 1 \leq N \leq 8
• 1 \leq S_i \leq 2718
• 1 \leq C_i \leq X \leq 5000
• 1 \leq P_i \leq 100
• All input values are integers.

Sample Input 1

3 2
100 1 50
200 1 20
1000 1 1

Sample Output 1

95

Consider the following submission strategy:

• First, submit to the 1st problem.
• If that submission is correct, submit to the 2nd problem; otherwise, submit again to the 1st problem.

The expected total score for this strategy is 95 points. No strategy can exceed an expected score of 95, so print 95.

Sample Input 2

2 7
100 3 50
100 2 50

Sample Output 2

125

Sample Input 3

5 32
500 9 57
300 4 8
300 3 32
300 7 99
100 8 69

Sample Output 3

953.976967020096

Sample Input 4

7 78
100 1 100
200 2 90
300 3 80
400 4 60
450 5 50
525 6 30
650 7 1

Sample Output 4

1976.2441416041121021

Problem Statement

We have a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

There are M kinds of operations available to you. Operation i swaps the a_i-th and b_i-th elements of P.

Is it possible to sort P in ascending order by doing at most 5\times 10^5 operations in total in any order?

If it is possible, give one such sequence of operations. Otherwise, report so.

Constraints

• 2\leq N \leq 1000
• P is a permutation of (1,2,\ldots,N).
• 1\leq M \leq \min(2\times 10^5, \frac{N(N-1)}{2})
• 1\leq a_i \lt b_i\leq N
• (a_i,b_i)\neq (a_j,b_j) if i\neq j.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3
4 2 1

P changes as follows: (5,3,2,4,6,1)\to (5,2,3,4,6,1)\to (5,2,3,4,1,6)\to (1,2,3,4,5,6).

Sample Input 2

5
3 4 1 2 5
2
1 3
2 5

Sample Output 2

-1

We cannot sort P in ascending order.

Sample Input 3

4
1 2 3 4
6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 3

0

P may already be sorted in ascending order.

Additionally, here is another accepted output:

4
5 5 5 5

Note that it is not required to minimize the number of operations.