Problem Statement

We held two competitions: Coding Contest and Robot Maneuver.

In each competition, the contestants taking the 3-rd, 2-nd, and 1-st places receive 100000, 200000, and 300000 yen (the currency of Japan), respectively. Furthermore, a contestant taking the first place in both competitions receives an additional 400000 yen.

DISCO-Kun took the X-th place in Coding Contest and the Y-th place in Robot Maneuver. Find the total amount of money he earned.

Constraints

• 1 \leq X \leq 205
• 1 \leq Y \leq 205
• X and Y are integers.

Sample Input 1

1 1

Sample Output 1

1000000

In this case, he earned 300000 yen in Coding Contest and another 300000 yen in Robot Maneuver. Furthermore, as he won both competitions, he got an additional 400000 yen. In total, he made 300000 + 300000 + 400000 = 1000000 yen.

Sample Input 2

3 101

Sample Output 2

100000

In this case, he earned 100000 yen in Coding Contest.

Sample Input 3

4 4

Sample Output 3

0

In this case, unfortunately, he was the highest-ranked contestant without prize money in both competitions.

Problem Statement

Takahashi, who works at DISCO, is standing before an iron bar. The bar has N-1 notches, which divide the bar into N sections. The i-th section from the left has a length of A_i millimeters.

Takahashi wanted to choose a notch and cut the bar at that point into two parts with the same length. However, this may not be possible as is, so he will do the following operations some number of times before he does the cut:

• Choose one section and expand it, increasing its length by 1 millimeter. Doing this operation once costs 1 yen (the currency of Japan).
• Choose one section of length at least 2 millimeters and shrink it, decreasing its length by 1 millimeter. Doing this operation once costs 1 yen.

Find the minimum amount of money needed before cutting the bar into two parts with the same length.

Constraints

• 2 \leq N \leq 200000
• 1 \leq A_i \leq 2020202020
• All values in input are integers.

Sample Input 1

3
2 4 3

Sample Output 1

3

The initial lengths of the sections are [2, 4, 3] (in millimeters). Takahashi can cut the bar equally after doing the following operations for 3 yen:

• Shrink the second section from the left. The lengths of the sections are now [2, 3, 3].
• Shrink the first section from the left. The lengths of the sections are now [1, 3, 3].
• Shrink the second section from the left. The lengths of the sections are now [1, 2, 3], and we can cut the bar at the second notch from the left into two parts of length 3 each.

Sample Input 2

12
100 104 102 105 103 103 101 105 104 102 104 101

Sample Output 2

0

Problem Statement

Chokudai made a rectangular cake for contestants in DDCC 2020 Finals.

The cake has H - 1 horizontal notches and W - 1 vertical notches, which divide the cake into H \times W equal sections. K of these sections has a strawberry on top of each of them.

The positions of the strawberries are given to you as H \times W characters s_{i, j} (1 \leq i \leq H, 1 \leq j \leq W). If s_{i, j} is #, the section at the i-th row from the top and the j-th column from the left contains a strawberry; if s_{i, j} is ., the section does not contain one. There are exactly K occurrences of #s.

Takahashi wants to cut this cake into K pieces and serve them to the contestants. Each of these pieces must satisfy the following conditions:

• Has a rectangular shape.
• Contains exactly one strawberry.

One possible way to cut the cake is shown below:

Find one way to cut the cake and satisfy the condition. We can show that this is always possible, regardless of the number and positions of the strawberries.

Constraints

• 1 \leq H \leq 300
• 1 \leq W \leq 300
• 1 \leq K \leq H \times W
• s_{i, j} is # or ..
• There are exactly K occurrences of # in s.

Sample Input 1

3 3 5
#.#
.#.
#.#

Sample Output 1

1 2 2
1 3 4
5 5 4

One way to cut this cake is shown below:

Sample Input 2

3 7 7
#...#.#
..#...#
.#..#..

Sample Output 2

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

One way to cut this cake is shown below:

Sample Input 3

13 21 106
.....................
.####.####.####.####.
..#.#..#.#.#....#....
..#.#..#.#.#....#....
..#.#..#.#.#....#....
.####.####.####.####.
.....................
.####.####.####.####.
....#.#..#....#.#..#.
.####.#..#.####.#..#.
.#....#..#.#....#..#.
.####.####.####.####.
.....................

Sample Output 3

12 12 23 34 45 45 60 71 82 93 93 2 13 24 35 35 17 28 39 50 50
12 12 23 34 45 45 60 71 82 93 93 2 13 24 35 35 17 28 39 50 50
12 12 56 89 89 89 60 104 82 31 31 46 13 24 35 35 61 61 39 50 50
12 12 67 67 100 100 60 9 9 42 42 57 13 24 6 72 72 72 72 72 72
12 12 78 5 5 5 20 20 20 53 68 68 90 24 6 83 83 83 83 83 83
16 16 27 38 49 49 64 75 86 97 79 79 90 101 6 94 94 105 10 21 21
16 16 27 38 49 49 64 75 86 97 79 79 90 101 6 94 94 105 10 21 21
32 32 43 54 65 65 80 11 106 95 22 22 33 44 55 55 70 1 96 85 85
32 32 43 54 76 76 91 11 106 84 84 4 99 66 66 66 81 1 96 74 74
14 14 3 98 87 87 102 11 73 73 73 4 99 88 77 77 92 92 63 63 63
25 25 3 98 87 87 7 29 62 62 62 15 99 88 77 77 103 19 30 52 52
36 36 47 58 69 69 18 29 40 51 51 26 37 48 59 59 8 19 30 41 41
36 36 47 58 69 69 18 29 40 51 51 26 37 48 59 59 8 19 30 41 41

Problem Statement

N programmers are going to participate in the preliminary stage of DDCC 20XX. Due to the size of the venue, however, at most 9 contestants can participate in the finals.

The preliminary stage consists of several rounds, which will take place as follows:

• All the N contestants will participate in the first round.
• When X contestants participate in some round, the number of contestants advancing to the next round will be decided as follows:
  • The organizer will choose two consecutive digits in the decimal notation of X, and replace them with the sum of these digits. The number resulted will be the number of contestants advancing to the next round.
    For example, when X = 2378, the number of contestants advancing to the next round will be 578 (if 2 and 3 are chosen), 2108 (if 3 and 7 are chosen), or 2315 (if 7 and 8 are chosen).
    When X = 100, the number of contestants advancing to the next round will be 10, no matter which two digits are chosen.
• The preliminary stage ends when 9 or fewer contestants remain.

Ringo, the chief organizer, wants to hold as many rounds as possible. Find the maximum possible number of rounds in the preliminary stage.

Since the number of contestants, N, can be enormous, it is given to you as two integer sequences d_1, \ldots, d_M and c_1, \ldots, c_M, which means the following: the decimal notation of N consists of c_1 + c_2 + \ldots + c_M digits, whose first c_1 digits are all d_1, the following c_2 digits are all d_2, \ldots, and the last c_M digits are all d_M.

Constraints

• 1 \leq M \leq 200000
• 0 \leq d_i \leq 9
• d_1 \neq 0
• d_i \neq d_{i+1}
• c_i \geq 1
• 2 \leq c_1 + \ldots + c_M \leq 10^{15}

Sample Input 1

2
2 2
9 1

Sample Output 1

3

In this case, N = 229 contestants will participate in the first round. One possible progression of the preliminary stage is as follows:

• 229 contestants participate in Round 1, 49 contestants participate in Round 2, 13 contestants participate in Round 3, and 4 contestants advance to the finals.

Here, three rounds take place in the preliminary stage, which is the maximum possible number.

Sample Input 2

3
1 1
0 8
7 1

Sample Output 2

9

In this case, 1000000007 will participate in the first round.

Problem Statement

This is an interactive task.

We have 2N balls arranged in a row, numbered 1, 2, 3, ..., 2N from left to right, where N is an odd number. Among them, there are N red balls and N blue balls.

While blindfolded, you are challenged to guess the color of every ball correctly, by asking at most 210 questions of the following form:

• You choose any N of the 2N balls and ask whether there are more red balls than blue balls or not among those N balls.

Now, let us begin.

Constraints

• 1 \leq N \leq 99
• N is an odd number.

Input and Output

First, receive the number of balls of each color, N, from Standard Input:

N

Then, ask questions until you find out the color of every ball. A question should be printed to Standard Output in the following format:

? A_1 A_2 A_3 ... A_N

This means that you are asking about the N balls A_1, A_2, A_3, ..., A_N, where 1 \leq A_i \leq 2N and A_i \neq A_j (i \neq j) must hold.

The response T to this question will be given from Standard Input in the following format:

T

Here T is one of the following strings:

• Red: Among the N balls chosen, there are more red balls than blue balls.
• Blue: Among the N balls chosen, there are more blue balls than red balls.
• -1: You printed an invalid question (including the case you asked more than 210 questions), or something else that was invalid.

If the judge returns -1, your submission is already judged as incorrect. The program should immediately quit in this case.

When you find out the color of every ball, print your guess to Standard Output in the following format:

! c_1c_2c_3...c_{2N}

Here c_i should be the character representing the color of Ball i; use R for red and B for blue.

Notice

• Flush Standard Output each time you print something. Failure to do so may result in TLE.
• Immediately terminate your program after printing your guess (or receiving the -1 response). Otherwise, the verdict will be indeterminate.
• If your program prints something invalid, the verdict will be indeterminate.

Sample Input and Output

In this sample, N = 3, and the colors of Ball 1, 2, 3, 4, 5, 6 are red, red, blue, blue, red, blue, respectively.

• In the first question, there are two red balls and one blue ball among the balls 1, 2, 3, so the judge returns Red.
• In the second question, there are one red ball and two blue balls among the balls 2, 4, 6, so the judge returns Blue.

Problem Statement

In 2937, DISCO creates a new universe called DISCOSMOS to celebrate its 1000-th anniversary.

DISCOSMOS can be described as an H \times W grid. Let (i, j) (1 \leq i \leq H, 1 \leq j \leq W) denote the square at the i-th row from the top and the j-th column from the left.

At time 0, one robot will be placed onto each square. Each robot is one of the following three types:

• Type-H: Does not move at all.
• Type-R: If a robot of this type is in (i, j) at time t, it will be in (i, j+1) at time t+1. If it is in (i, W) at time t, however, it will be instead in (i, 1) at time t+1. (The robots do not collide with each other.)
• Type-D: If a robot of this type is in (i, j) at time t, it will be in (i+1, j) at time t+1. If it is in (H, j) at time t, however, it will be instead in (1, j) at time t+1.

There are 3^{H \times W} possible ways to place these robots. In how many of them will every square be occupied by one robot at times 0, T, 2T, 3T, 4T, and all subsequent multiples of T?

Since the count can be enormous, compute it modulo (10^9 + 7).

Constraints

• 1 \leq H \leq 10^9
• 1 \leq W \leq 10^9
• 1 \leq T \leq 10^9
• H, W, T are all integers.

Sample Input 1

2 2 1

Sample Output 1

9

Shown below are some of the ways to place the robots that satisfy the condition, where ., >, and v stand for Type-H, Type-R, and Type-D, respectively:

>>  ..  vv
..  ..  vv

Sample Input 2

869 120 1001

Sample Output 2

672919729