Problem Statement

Mr. AtCoder reads in the newspaper that today's lucky number is a positive integer A and tomorrow's is a positive integer B.

Here, he defines a positive integer x that satisfies both of the following conditions as a super-lucky number.

• The decimal notation of x contains A as a contiguous substring.
• The decimal notation of 2x contains B as a contiguous substring.

Actually, under the Constraints of this problem, there is always a super-lucky number less than 10^{18}. Find one such number.

Constraints

• 1 \leq A < 10^8
• 1 \leq B < 10^8
• A and B have no leading 0s.
• All values in input are integers.

Sample Input 1

13
62

Sample Output 1

131

One super-lucky number is x = 131, because:

• x = 131 contains 13 as a substring. (1-st through 2-nd characters)
• 2x = 262 contains 62 as a substring. (2-nd through 3-rd characters)

Some other super-lucky numbers are 313, 8135, and 135797531, which would also be accepted.

Sample Input 2

69120
824

Sample Output 2

869120

One super-lucky number is x = 869120, because:

• x = 869120 contains 69120 as a substring. (2-nd through 6-th characters)
• 2x = 1738240 contains 824 as a substring. (4-th through 6-th characters)

The smallest super-lucky number is 69120, but note that any lucky number with at most 18 digits would be accepted.

Sample Input 3

6283185
12566370

Sample Output 3

6283185

When x = 6283185, x is A itself, and 2x is B itself. In such a case too, x is a super-lucky number.

Problem Statement

We have a canvas represented as a H \times W grid. Let (i, j) denote the square at the i-th row (1 \leq i \leq H) from the top and j-th column (1 \leq j \leq W) from the left.

Initially, (i, j) is in the following state.

• If c_{i, j}=1: painted in Color 1.
• If c_{i, j}=2: painted in Color 2.
• If c_{i, j}=3: painted in Color 3.
• If c_{i, j}=4: painted in Color 4.
• If c_{i, j}=5: painted in Color 5.
• If c_{i, j}=.: not yet painted.

Create a way to paint each unpainted square in Color 1, 2, 3, 4, or 5 so that no two horizontally or vertically adjacent squares have the same color. It is not allowed to change the color of a square that is already painted.

Constraints

• 1 \leq H, W \leq 700
• c_{i, j} is 1, 2, 3, 4, 5, or ..
• At least one square is unpainted.
• There is at least one way to paint the squares under the condition.

Sample Input 1

3 3
...
...
...

Sample Output 1

132
313
541

Sample Output 1 corresponds to the following coloring.

Sample Input 2

5 7
1.2.3.4
.5.1.2.
3.4.5.1
.2.3.4.
5.1.2.3

Sample Output 2

1425314
2531425
3142531
4253142
5314253

Sample Output 2 corresponds to the following coloring.

Sample Input 3

1 1
.

Sample Output 3

4

Problem Statement

There are N cookies on a desk. Each cookie has a positive integer on its surface: A_1, A_2, \dots, A_N, which are all different.

Let us play a game with two players using these cookies. In this game, the players alternately do the following action.

Choose a cookie on the desk and eat it. Then, if the \mathrm{XOR} of the integers written on the remaining cookies on the desk becomes 0, the player wins, and the game ends.

You have asked the boy E869120 to play this game with you. You go first, and E869120 goes second. Are you going to win if both players play optimally?

Constraints

• 1 \leq N \leq 400000
• 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
• A_1, A_2, \dots, A_N are all different.
• The \mathrm{XOR} of A_1, A_2, \dots, A_N is not 0.
• All values in input are integers.

Sample Input 1

6
9 14 11 3 5 8

Sample Output 1

Lose

In this case, regardless of what choices you make, you will lose if E869120 keeps playing optimally.

For example, let us say you first eat the cookie with 11 written on it. Then, E869120 will eat the cookie with 9 so that the \mathrm{XOR} of the numbers written on the remaining cookies, 14, 3, 5, 8, is 0, making him win.

Even if you make other choices, E869120 will win eventually.

Sample Input 2

1
131

Sample Output 2

Win

In this case, your only choice in your first turn is to eat the cookie with 131. Then, there is no more cookie on the desk, making the \mathrm{XOR} of the numbers written on the remaining cookies 0. Therefore, before E869120 gets to do anything, you win.

Sample Input 3

8
12 23 34 45 56 78 89 98

Sample Output 3

Win

Problem Statement

Ringo is participating in an archery contest AtArcher.

In AtArcher, a participant shoots N arrows at a target on a number line to compete for the total score. The center of the target is at coordinate 0. Based on where the arrow hits, the score of the shot is defined as follows.

• For i = 0, 1, \dots, M-1, if the arrow hits a point whose distance from the center of the target is between r_i and r_{i+1}, the score is s_i. If the distance is greater than r_M, the score is 0. If the arrow hits the boundary, the higher score is applied.
• The closer to the center, the higher the score is. In other words, the following is satisfied.
  • 0 = r_0 \lt r_1 \lt \cdots \lt r_{M-1} \lt r_M
  • s_0 \gt s_1 \gt \cdots \gt s_{M-1} \gt 0

For example, the figure below shows the score for a shot when r = (0, 2, 7, 9), s = (100, 70, 30).

Additionally, AtArcher has one special rule: the distance between any two arrows must always be at least D. Violating this rule disqualifies the participant, making the total score 0.

What is the maximum total score that Ringo can get from all the shots?

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq D \leq 10^6
• 0 = r_0 \lt r_1 \lt \cdots \lt r_{M-1} \lt r_M \leq 10^{11}
• 10^{11} \geq s_0 \gt s_1 \gt \cdots \gt s_{M-1} \gt 0
• All values in input are integers.

Sample Input 1

3 3 3
0 2 7 9
100 70 30

Sample Output 1

270

This sample input corresponds to the case in the Problem Statement, with D = 3.

For example, if the N = 3 arrows hit the coordinates -6, -2, 1, they score 70, 100, 100, respectively, for a total score of 270, which is the maximum achievable.

Note that you cannot hit the 100-point area with all the arrows to score 300, because the distance between any two arrows must be at least D = 3, or you will be disqualified and score 0.

Sample Input 2

3 3 8
0 2 7 9
100 70 30

Sample Output 2

200

This sample input corresponds to the case in the Problem Statement, with D = 8.

For example, if the N = 3 arrows hit the coordinates -7, 1, 9, they score 70, 100, 30, respectively, for a total score of 200, which is the maximum achievable.

Sample Input 3

7 5 47
0 10 40 100 160 220
50 25 9 6 3

Sample Output 3

111

For example, if you shoot the arrows as shown in the following figure, you will score 111 in total, which is the maximum.

Sample Input 4

100 1 5
0 7
100000000000

Sample Output 4

300000000000

You can shoot N = 100 arrows, but in order to avoid disqualification, at most 3 arrows can hit the area with a positive score.

Sample Input 5

15 10 85
0 122 244 366 488 610 732 854 976 1098 1220
10 9 8 7 6 5 4 3 2 1

Sample Output 5

119

Problem Statement

Takahashi has Christmas decoration consisting of N balls and \frac{N(N-1)}{2} ropes. The balls are numbered 1 to N, and for any two different balls, there is exactly one rope that connects them.

He decides to light up each rope in red, blue, or white.

For better appearance, he wants to satisfy all of the following conditions.

Condition 1 the numbers of ropes lighted in red, blue, and white are all equal.

Condition 2 there is no triple of integers a, b, c (1 \leq a < b < c \leq N) such that all of the following three ropes have different colors:

• the rope connecting a and b,
• the rope connecting b and c,
• the rope connecting a and c.

Create a way to light up the ropes to satisfy the conditions. If there is no such way, report so.

Constraints

• 3 \leq N \leq 50
• N is an integer.

Sample Input 1

4

Sample Output 1

No

For N=4, there is no way to light up the ropes to satisfy the conditions, so the output No is correct.

Below is an example of an output in the Yes case, which is incorrect in this case. This is because, for (a, b, c) = (1, 2, 3) in Condition 2, the rope connecting a, b is red, the rope connecting b, c is white, and the rope connecting a, c is blue, all of which have different colors.

Yes
RBW
WB
R

Problem Statement

On a string S consisting of A, R, and C, we did the following operation at most K times: choose three consecutive characters and overwrite them with ARC. The result is the string T.

How many strings are there that could be the initial string S? Find this count modulo 998244353.

Constraints

• 3 \leq |T| \leq 5000
• 0 \leq K \leq 10000
• T is a string consisting of A, R, and C.

Sample Input 1

ARCCARC
1

Sample Output 1

53

Below are some examples of the initial string S from which we can get the string T = ARCCARC with at most 1 operation.

• S = ARCCARC: we can choose to do nothing to get ARCCARC.
• S = CRACARC: we can choose the 1-st, 2-nd, 3-rd characters and overwrite them with ARC to get ARCCARC.
• S = ARCCCCC: we can choose the 5-th, 6-th, 7-th characters and overwrite them with ARC to get ARCCARC.

There are many other strings that could be S, for a total of 53.

Sample Input 2

ARARCRCA
5

Sample Output 2

2187

If the intial string S is AAAAAAAA, one way to get T = ARARCRCA with at most 5 operations is as follows.

• Step 1: choose the 3-rd, 4-th, 5-th characters and overwrite them with ARC to get the string AAARCAAA.
• Step 2: choose the 5-th, 6-th, 7-th characters and overwrite them with ARC to get the string AAARARCA.
• Step 3: choose the 1-st, 2-nd, 3-rd characters and overwrite them with ARC to get the string ARCRARCA.
• Step 4: choose the 3-rd, 4-th, 5-th characters and overwrite them with ARC to get the string ARARCRCA.

There are many other strings that could be S, for a total of 2187.

Sample Input 3

AARCRRARCC
0

Sample Output 3

1

We can get T = AARCRRARCC with 0 operations in only one case in which S = T from the beginning, or S = AARCRRARCC.

Sample Input 4

AAAAARRRRRCCCCC
131

Sample Output 4

1

In this case, there is just one string that could be S: AAAAARRRRRCCCCC.

Sample Input 5

CAARCACRAAARARARCRCRARCARARCRRARC
9

Sample Output 5

797833187

There are 320236026147 strings that could be S, so print this count modulo 998244353, which is 797833187.