Your task is to process some data.
You are given 3 integers a , b , c and a string s. Output result of a + b + c and string s with a half-width break.

Constraints

• 1\leq a, b, c \leq 1,000
• 1\leq |s| \leq 100

Output the result of a+b+c and string s with a half-width break in one line.

Input Example #1

1
2 3
test

Output Example #1

6 test

• 1+2+3 equals to 6.

Input Example #2

72
128 256
myonmyon

Output Example #2

456 myonmyon

• 72+128+256 equals to 456.

Problem Statement

AtCoDeer the deer found two positive integers, a and b. Determine whether the product of a and b is even or odd.

Constraints

• 1 ≤ a,b ≤ 10000
• a and b are integers.

Sample Input 1

3 4

Sample Output 1

Even

As 3 × 4 = 12 is even, print Even.

Sample Input 2

1 21

Sample Output 2

Odd

As 1 × 21 = 21 is odd, print Odd.

Problem Statement

Snuke has a grid consisting of three squares numbered 1, 2 and 3. In each square, either 0 or 1 is written. The number written in Square i is s_i.

Snuke will place a marble on each square that says 1. Find the number of squares on which Snuke will place a marble.

Constraints

• Each of s_1, s_2 and s_3 is either 1 or 0.

Sample Input 1

101

Sample Output 1

2

• A marble will be placed on Square 1 and 3.

Sample Input 2

000

Sample Output 2

0

• No marble will be placed on any square.

Problem Statement

There are N positive integers written on a blackboard: A_1, ..., A_N.

Snuke can perform the following operation when all integers on the blackboard are even:

• Replace each integer X on the blackboard by X divided by 2.

Find the maximum possible number of operations that Snuke can perform.

Constraints

• 1 \leq N \leq 200
• 1 \leq A_i \leq 10^9

Sample Input 1

3
8 12 40

Sample Output 1

2

Initially, [8, 12, 40] are written on the blackboard. Since all those integers are even, Snuke can perform the operation.

After the operation is performed once, [4, 6, 20] are written on the blackboard. Since all those integers are again even, he can perform the operation.

After the operation is performed twice, [2, 3, 10] are written on the blackboard. Now, there is an odd number 3 on the blackboard, so he cannot perform the operation any more.

Thus, Snuke can perform the operation at most twice.

Sample Input 2

4
5 6 8 10

Sample Output 2

0

Since there is an odd number 5 on the blackboard already in the beginning, Snuke cannot perform the operation at all.

Sample Input 3

6
382253568 723152896 37802240 379425024 404894720 471526144

Sample Output 3

8

Problem Statement

You have A 500-yen coins, B 100-yen coins and C 50-yen coins (yen is the currency of Japan). In how many ways can we select some of these coins so that they are X yen in total?

Coins of the same kind cannot be distinguished. Two ways to select coins are distinguished when, for some kind of coin, the numbers of that coin are different.

Constraints

• 0 \leq A, B, C \leq 50
• A + B + C \geq 1
• 50 \leq X \leq 20 000
• A, B and C are integers.
• X is a multiple of 50.

Sample Input 1

2
2
2
100

Sample Output 1

2

There are two ways to satisfy the condition:

• Select zero 500-yen coins, one 100-yen coin and zero 50-yen coins.
• Select zero 500-yen coins, zero 100-yen coins and two 50-yen coins.

Sample Input 2

5
1
0
150

Sample Output 2

0

Note that the total must be exactly X yen.

Sample Input 3

30
40
50
6000

Sample Output 3

213

Problem Statement

Find the sum of the integers between 1 and N (inclusive), whose sum of digits written in base 10 is between A and B (inclusive).

Constraints

• 1 \leq N \leq 10^4
• 1 \leq A \leq B \leq 36
• All input values are integers.

Sample Input 1

20 2 5

Sample Output 1

84

Among the integers not greater than 20, the ones whose sums of digits are between 2 and 5, are: 2,3,4,5,11,12,13,14 and 20. We should print the sum of these, 84.

Sample Input 2

10 1 2

Sample Output 2

13

Sample Input 3

100 4 16

Sample Output 3

4554

Problem Statement

We have N cards. A number a_i is written on the i-th card.
Alice and Bob will play a game using these cards. In this game, Alice and Bob alternately take one card. Alice goes first.
The game ends when all the cards are taken by the two players, and the score of each player is the sum of the numbers written on the cards he/she has taken. When both players take the optimal strategy to maximize their scores, find Alice's score minus Bob's score.

Constraints

• N is an integer between 1 and 100 (inclusive).
• a_i \ (1 \leq i \leq N) is an integer between 1 and 100 (inclusive).

Sample Input 1

2
3 1

Sample Output 1

2

First, Alice will take the card with 3. Then, Bob will take the card with 1. The difference of their scores will be 3 - 1 = 2.

Sample Input 2

3
2 7 4

Sample Output 2

5

First, Alice will take the card with 7. Then, Bob will take the card with 4. Lastly, Alice will take the card with 2. The difference of their scores will be 7 - 4 + 2 = 5. The difference of their scores will be 3 - 1 = 2.

Sample Input 3

4
20 18 2 18

Sample Output 3

18

Problem Statement

An X-layered kagami mochi (X ≥ 1) is a pile of X round mochi (rice cake) stacked vertically where each mochi (except the bottom one) has a smaller diameter than that of the mochi directly below it. For example, if you stack three mochi with diameters of 10, 8 and 6 centimeters from bottom to top in this order, you have a 3-layered kagami mochi; if you put just one mochi, you have a 1-layered kagami mochi.

Lunlun the dachshund has N round mochi, and the diameter of the i-th mochi is d_i centimeters. When we make a kagami mochi using some or all of them, at most how many layers can our kagami mochi have?

Constraints

• 1 ≤ N ≤ 100
• 1 ≤ d_i ≤ 100
• All input values are integers.

Sample Input 1

4
10
8
8
6

Sample Output 1

3

If we stack the mochi with diameters of 10, 8 and 6 centimeters from bottom to top in this order, we have a 3-layered kagami mochi, which is the maximum number of layers.

Sample Input 2

3
15
15
15

Sample Output 2

1

When all the mochi have the same diameter, we can only have a 1-layered kagami mochi.

Sample Input 3

7
50
30
50
100
50
80
30

Sample Output 3

4

Problem Statement

The commonly used bills in Japan are 10000-yen, 5000-yen and 1000-yen bills. Below, the word "bill" refers to only these.

According to Aohashi, he received an otoshidama (New Year money gift) envelope from his grandfather that contained N bills for a total of Y yen, but he may be lying. Determine whether such a situation is possible, and if it is, find a possible set of bills contained in the envelope. Assume that his grandfather is rich enough, and the envelope was large enough.

Constraints

• 1 ≤ N ≤ 2000
• 1000 ≤ Y ≤ 2 × 10^7
• N is an integer.
• Y is a multiple of 1000.

Sample Input 1

9 45000

Sample Output 1

4 0 5

If the envelope contained 4 10000-yen bills and 5 1000-yen bills, he had 9 bills and 45000 yen in total. It is also possible that the envelope contained 9 5000-yen bills, so the output 0 9 0 is also correct.

Sample Input 2

20 196000

Sample Output 2

-1 -1 -1

When the envelope contained 20 bills in total, the total value would be 200000 yen if all the bills were 10000-yen bills, and would be at most 195000 yen otherwise, so it would never be 196000 yen.

Sample Input 3

1000 1234000

Sample Output 3

14 27 959

There are also many other possibilities.

Sample Input 4

2000 20000000

Sample Output 4

2000 0 0

Problem Statement

You are given a string S consisting of lowercase English letters. Another string T is initially empty. Determine whether it is possible to obtain S = T by performing the following operation an arbitrary number of times:

• Append one of the following at the end of T: dream, dreamer, erase and eraser.

Constraints

• 1≦|S|≦10^5
• S consists of lowercase English letters.

Sample Input 1

erasedream

Sample Output 1

YES

Append erase and dream at the end of T in this order, to obtain S = T.

Sample Input 2

dreameraser

Sample Output 2

YES

Append dream and eraser at the end of T in this order, to obtain S = T.

Sample Input 3

dreamerer

Sample Output 3

NO

Problem Statement

AtCoDeer the deer is going on a trip in a two-dimensional plane. In his plan, he will depart from point (0, 0) at time 0, then for each i between 1 and N (inclusive), he will visit point (x_i,y_i) at time t_i.

If AtCoDeer is at point (x, y) at time t, he can be at one of the following points at time t+1: (x+1,y), (x-1,y), (x,y+1) and (x,y-1). Note that he cannot stay at his place. Determine whether he can carry out his plan.

Constraints

• 1 ≤ N ≤ 10^5
• 0 ≤ x_i ≤ 10^5
• 0 ≤ y_i ≤ 10^5
• 1 ≤ t_i ≤ 10^5
• t_i < t_{i+1} (1 ≤ i ≤ N-1)
• All input values are integers.

Sample Input 1

2
3 1 2
6 1 1

Sample Output 1

Yes

For example, he can travel as follows: (0,0), (0,1), (1,1), (1,2), (1,1), (1,0), then (1,1).

Sample Input 2

1
2 100 100

Sample Output 2

No

It is impossible to be at (100,100) two seconds after being at (0,0).

Sample Input 3

2
5 1 1
100 1 1

Sample Output 3

No

Problem Statement

This is an interactive task. Please note that these are not beginner questions.

If you are a beginner, try the AtCoder Beginners Selection!

There are N balls labeled with the first N uppercase letters. The balls have pairwise distinct weights.

You are allowed to ask at most Q queries. In each query, you can compare the weights of two balls (see Input/Output section for details).

Sort the balls in the ascending order of their weights.

Constraints

• (N, Q) = (26, 1000), (26, 100), or (5, 7).

Partial Score

There are three testsets. Each testset is worth 100 points.

• In testset 1, N = 26 and Q = 1000.
• In testset 2, N = 26 and Q = 100.
• In testset 3, N = 5 and Q = 7.

Input and Output

First, you are given N and Q from Standard Input in the following format:

N Q

Then, you start asking queries (at most Q times). Each query must be printed to Standard Output in the following format:

? c_1 c_2

Here each of c_1 and c_2 must be one of the first N uppercase letters, and c_1 and c_2 must be distinct.

Then, you are given the answer to the query from Standard Input in the following format:

ans

Here ans is either < or >. When ans is <, the ball c_2 is heavier than the ball c_1, and otherwise the ball c_1 is heavier than the ball c_2.

Finally, you must print the answer to Standard Output in the following format:

! ans

Here ans must be a string of length N, and it must contain each of the first N uppercase letters once. It must represent the weights of the balls in the ascending order.

Judgement

• After each output, you must flush Standard Output. Otherwise you may get TLE.
• After you print the answer, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.
• When your output is invalid or incorrect, the behavior of the judge is undefined (it does not necessarily give WA).

Sample Code

Here is a sample solution for 100 points. The code is obtainable for partial points, so submitting it will result in a WA.

#include <cstdio>
#include <string>

using namespace std;

int main(void){
  int N,Q,i,j;

  scanf("%d%d", &N, &Q);

  string s;
  for(i=0;i<N;i++) s += (char)('A' + i);

  for(i=0;i<N;i++) for(j=0;j<N-1;j++){
    printf("? %c %c\n", s[j], s[j+1]);
    fflush(stdout);
    char ans;
    scanf(" %c", &ans);
    if(ans == '>') swap(s[j], s[j+1]);
  }

  printf("! %s\n", s.c_str());
  fflush(stdout);

  return 0;
}

Sample

In this sample N = 3, Q = 10, and the answer is BAC.

Problem Statement

You are given an undirected graph with N vertices and 0 edges. Process Q queries of the following types.

• 0 u v: Add an edge (u, v).
• 1 u v: Print 1 if u and v are in the same connected component, 0 otherwise.

Constraints

• 1 \leq N \leq 200,000
• 1 \leq Q \leq 200,000
• 0 \leq u_i, v_i \lt N

Sample Input 1

4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3

Sample Output 1

0
1
0
1

Problem Statement

You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

• 0 p x: a_p \gets a_p + x
• 1 l r: Print \sum_{i = l}^{r - 1}{a_i}.

Constraints

• 1 \leq N, Q \leq 500,000
• 0 \leq a_i, x \leq 10^9
• 0 \leq p < N
• 0 \leq l_i < r_i \leq N
• All values in Input are integer.

Sample Input 1

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

Sample Output 1

15
7
25
6

Problem Statement

In this problem, you should process T testcases.

For each testcase, you are given four integers N, M, A, B.

Calculate \sum_{i = 0}^{N - 1} floor((A \times i + B) / M).

Constraints

• 1 \leq T \leq 100,000
• 1 \leq N, M \leq 10^9
• 0 \leq A, B < M

Sample Input 1

5
4 10 6 3
6 5 4 3
1 1 0 0
31415 92653 58979 32384
1000000000 1000000000 999999999 999999999

Sample Output 1

3
13
0
314095480
499999999500000000

Problem Statement

You are given a grid of N rows and M columns. The square at the i-th row and j-th column will be denoted as (i,j). Some of the squares contain an object. All the remaining squares are empty. The state of the grid is represented by strings S_1,S_2,\cdots,S_N. The square (i,j) contains an object if S_{i,j}= # and is empty if S_{i,j}= ..

Consider placing 1 \times 2 tiles on the grid. Tiles can be placed vertically or horizontally to cover two adjacent empty squares. Tiles must not stick out of the grid, and no two different tiles may intersect. Tiles cannot occupy the square with an object.

Calculate the maximum number of tiles that can be placed and any configulation that acheives the maximum.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• S_i is a string with length M consists of # and ..

Sample Input 1

3 3
#..
..#
...

Sample Output 1

3
#><
vv#
^^.

The following output is also treated as a correct answer.

3
#><
v.#
^><

Problem Statement

You are given a grid of N rows and M columns. The square at the i-th row and j-th column will be denoted as (i,j). A nonnegative integer A_{i,j} is written for each square (i,j).

You choose some of the squares so that each row and column contains at most K chosen squares. Under this constraint, calculate the maximum value of the sum of the integers written on the chosen squares. Additionally, calculate a way to choose squares that acheives the maximum.

Constraints

• 1 \leq N \leq 50
• 1 \leq K \leq N
• 0 \leq A_{i,j} \leq 10^9
• All values in Input are integer.

Sample Input 1

3 1
5 3 2
1 4 8
7 6 9

Sample Output 1

19
X..
..X
.X.

Sample Input 2

3 2
10 10 1
10 10 1
1 1 10

Sample Output 2

50
XX.
XX.
..X

Problem Statement

You are given two integer arrays a_0, a_1, ..., a_{N - 1} and b_0, b_1, ..., b_{M - 1}. Calculate the array c_0, c_1, ..., c_{(N - 1) + (M - 1)}, defined by c_i = \sum_{j = 0}^i a_j b_{i - j} \bmod 998244353.

Constraints

• 1 \leq N, M \leq 524288
• 0 \leq a_i, b_i < 998244353
• All values in Input are integer.

Sample Input 1

4 5
1 2 3 4
5 6 7 8 9

Sample Output 1

5 16 34 60 70 70 59 36

Sample Input 2

1 1
10000000
10000000

Sample Output 2

871938225

Problem Statement

You are given a directed graph with N vertices and M edges, not necessarily simple. The i-th edge is oriented from the vertex a_i to the vertex b_i. Divide this graph into strongly connected components and print them in their topological order.

Constraints

• 1 \leq N \leq 500,000
• 1 \leq M \leq 500,000
• 0 \leq a_i, b_i < N

Sample Input 1

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

Sample Output 1

4
1 5
2 4 1
1 2
2 3 0

Problem Statement

Consider placing N flags on a line. Flags are numbered through 1 to N.

Flag i can be placed on the coordinate X_i or Y_i. For any two different flags, the distance between them should be at least D.

Decide whether it is possible to place all N flags. If it is possible, print such a configulation.

Constraints

• 1 \leq N \leq 1000
• 0 \leq D \leq 10^9
• 0 \leq X_i < Y_i \leq 10^9
• All values in Input are integer.

Sample Input 1

3 2
1 4
2 5
0 6

Sample Output 1

Yes
4
2
0

Sample Input 2

3 3
1 4
2 5
0 6

Sample Output 2

No

Problem Statement

You are given a string of length N. Calculate the number of distinct substrings of S.

Constraints

• 1 \leq N \leq 500,000
• S consists of lowercase English letters.

Sample Input 1

abcbcba

Sample Output 1

21

Sample Input 2

mississippi

Sample Output 2

53

Sample Input 3

ababacaca

Sample Output 3

33

Sample Input 4

aaaaa

Sample Output 4

5

Problem Statement

You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

The type of i-th query is represented by T_i.

• T_i=1: You are given two integers X_i,V_i. Replace the value of A_{X_i} with V_i.
• T_i=2: You are given two integers L_i,R_i. Calculate the maximum value among A_{L_i},A_{L_i+1},\cdots,A_{R_i}.
• T_i=3: You are given two integers X_i,V_i. Calculate the minimum j such that X_i \leq j \leq N, V_i \leq A_j. If there is no such j, answer j=N+1 instead.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq T_i \leq 3
• 1 \leq X_i \leq N, 0 \leq V_i \leq 10^9 (T_i=1,3)
• 1 \leq L_i \leq R_i \leq N (T_i=2)
• All values in Input are integer.

Sample Input 1

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

Sample Output 1

3
3
2
6

• First query: Print 3, which is the maximum of (A_1,A_2,A_3,A_4,A_5)=(1,2,3,2,1).
• Second query: Since 3>A_2, j=2 does not satisfy the condition．Since 3 \leq A_3, print j=3.
• Third query: Replace the value of A_3 with 1. It becomes A=(1,2,1,2,1).
• Fourth query: Print 2, which is the maximum of (A_2,A_3,A_4)=(2,1,2).
• Fifth query: Since there is no j that satisfies the condition, print j=N+1=6.

Problem Statement

You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

• 0 l r b c: For each i = l, l+1, \dots, {r - 1}, set a_i \gets b \times a_i + c.
• 1 l r: Print \sum_{i = l}^{r - 1} a_i \bmod 998244353.

Constraints

• 1 \leq N, Q \leq 500000
• 0 \leq a_i, c < 998244353
• 1 \leq b < 998244353
• 0 \leq l < r \leq N
• All values in Input are integer.

Sample Input 1

5 7
1 2 3 4 5
1 0 5
0 2 4 100 101
1 0 3
0 1 3 102 103
1 2 5
0 2 5 104 105
1 0 5

Sample Output 1

15
404
41511
4317767

Problem Statement

You are given a binary array A=(A_1,A_2,\cdots,A_N) of length N.

Process Q queries of the following types. The i-th query is represented by three integers T_i,L_i,R_i.

• T_i=1: Replace the value of A_j with 1-A_j for each L_i \leq j \leq R_i.
• T_i=2: Calculate the inversion(*) of the array A_{L_i},A_{L_i+1},\cdots,A_{R_i}．

Note：The inversion of the array x_1,x_2,\cdots,x_k is the number of the pair of integers i,j with 1 \leq i < j \leq k, x_i > x_j.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 1
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq T_i \leq 2
• 1 \leq L_i \leq R_i \leq N
• All values in Input are integer.

Sample Input 1

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

Sample Output 1

2
0
1

• First query: Print 2, which is the inversion of (A_1,A_2,A_3,A_4,A_5)=(0,1,0,0,1).
• Second query: Replace the value of A_3 and A_4 with 1 and 1, respectively.
• Third query: Print 0, which is the inversion of (A_2,A_3,A_4,A_5)=(1,1,1,1).
• Fourth query: Replace the value of A_1, A_2 and A_4 with 1, 0 and 0, respectively.
• Fifth query: Print 1, which is the inversion of (A_1,A_2)=(1,0).

Problem Statement

In an xy-coordinate plane whose x-axis is oriented to the right and whose y-axis is oriented upwards, rotate a point (a, b) around the origin d degrees counterclockwise and find the new coordinates of the point.

Constraints

• -1000 \leq a,b \leq 1000
• 1 \leq d \leq 360
• All values in input are integers.

Sample Input 1

2 2 180

Sample Output 1

-2 -2

When (2, 2) is rotated around the origin 180 degrees counterclockwise, it becomes the symmetric point of (2, 2) with respect to the origin, which is (-2, -2).

Sample Input 2

5 0 120

Sample Output 2

-2.49999999999999911182 4.33012701892219364908

When (5, 0) is rotated around the origin 120 degrees counterclockwise, it becomes (-\frac {5}{2} , \frac {5\sqrt{3}}{2}).
This sample output does not precisely match these values, but the errors are small enough to be considered correct.

Sample Input 3

0 0 11

Sample Output 3

0.00000000000000000000 0.00000000000000000000

Since (a, b) is the origin (the center of rotation), a rotation does not change its coordinates.

Sample Input 4

15 5 360

Sample Output 4

15.00000000000000177636 4.99999999999999555911

A 360-degree rotation does not change the coordinates of a point.

Sample Input 5

-505 191 278

Sample Output 5

118.85878514480690171240 526.66743699786547949770

Problem Statement

Takahashi and Aoki will play the following game against each other.

Starting from Takahashi, the two alternatingly declare an integer between 1 and 2N+1 (inclusive) until the game ends. Any integer declared by either player cannot be declared by either player again. The player who is no longer able to declare an integer loses; the player who didn't lose wins.

In this game, Takahashi will always win. Your task is to actually play the game on behalf of Takahashi and win the game.

Constraints

• 1 \leq N \leq 1000
• N is an integer.

Input and Output

This task is an interactive task (in which your program and the judge program interact with each other via inputs and outputs).
Your program plays the game on behalf of Takahashi, and the judge program plays the game on behalf of Aoki.

First, your program is given a positive integer N from Standard Input. Then, the following procedures are repeated until the game ends.

1. Your program outputs an integer between 1 and 2N+1 (inclusive) to Standard Output, which defines the integer that Takahashi declares. (You cannot output an integer that is already declared by either player.)
2. The integer that Aoki declares is given by the judge program to your program from Standard Input. (No integer that is already declared by either player will be given.) If Aoki has no more integer to declare, 0 is given instead, which means that the game ended and Takahashi won.

Notes

• After each output, you must flush Standard Output. Otherwise, you may get TLE.
• After the game ended and Takahashi won, the program must be terminated immediately. Otherwise, the judge does not necessarily give AC.
• If your program outputs something that violates the rules of the game (such as an integer that has already been declared by either player), your answer is considered incorrect. In such case, the verdict is indeterminate. It does not necessarily give WA.

Sample Input and Output

Problem Statement

Given N integers A_1, ..., A_N, compute A_1 \times ... \times A_N.

However, if the result exceeds 10^{18}, print -1 instead.

Constraints

• 2 \leq N \leq 10^5
• 0 \leq A_i \leq 10^{18}
• All values in input are integers.

Sample Input 1

2
1000000000 1000000000

Sample Output 1

1000000000000000000

We have 1000000000 \times 1000000000 = 1000000000000000000.

Sample Input 2

3
101 9901 999999000001

Sample Output 2

-1

We have 101 \times 9901 \times 999999000001 = 1000000000000000001, which exceeds 10^{18}, so we should print -1 instead.

Sample Input 3

31
4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0

Sample Output 3

0

Problem Statement

There is a board game with N+1 squares: square 0, square 1, \dots, square N.
You have a die (dice) that rolls an integer between 1 and K, inclusive, with equal probability for each outcome.
You start on square 0. You repeat the following operation until you reach square N:

• Roll the dice. Let x be the current square and y be the rolled number, then move to square \min(N, x + y).

Let P_i be the probability of reaching square N after exactly i operations. Calculate P_1, P_2, \dots, P_N modulo 998244353.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• N and K are integers.

Sample Input 1

3 2

Sample Output 1

0
249561089
748683265

For example, you reach square N after exactly two operations when the die rolls the following numbers:

• A 1 on the first operation, and a 2 on the second operation.
• A 2 on the first operation, and a 1 on the second operation.
• A 2 on the first operation, and a 2 on the second operation.

Therefore, P_2 = \left( \frac{1}{2} \times \frac{1}{2} \right) \times 3 = \frac{3}{4}. We have 249561089 \times 4 \equiv 3 \pmod{998244353}, so print 249561089 for P_2.

Sample Input 2

5 5

Sample Output 2

598946612
479157290
463185380
682000542
771443236

Sample Input 3

10 6

Sample Output 3

0
166374059
207967574
610038216
177927813
630578223
902091444
412046453
481340945
404612686

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.
Initially, there is one wall in each cell.
After processing Q queries explained below in the order they are given, find the number of remaining walls.

In the q-th query, you are given two integers R_q and C_q.
You place a bomb at (R_q, C_q) to destroy walls. As a result, the following process occurs.

• If there is a wall at (R_q, C_q), destroy that wall and end the process.
• If there is no wall at (R_q, C_q), destroy the first walls that appear when looking up, down, left, and right from (R_q, C_q). More precisely, the following four processes occur simultaneously:
  • If there exists an i \lt R_q such that a wall exists at (i, C_q) and no wall exists at (k, C_q) for all i \lt k \lt R_q, destroy the wall at (i, C_q).
  • If there exists an i \gt R_q such that a wall exists at (i, C_q) and no wall exists at (k, C_q) for all R_q \lt k \lt i, destroy the wall at (i, C_q).
  • If there exists a j \lt C_q such that a wall exists at (R_q, j) and no wall exists at (R_q, k) for all j \lt k \lt C_q, destroy the wall at (R_q, j).
  • If there exists a j \gt C_q such that a wall exists at (R_q, j) and no wall exists at (R_q, k) for all C_q \lt k \lt j, destroy the wall at (R_q, j).

Constraints

• 1 \leq H, W
• H \times W \leq 4 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq R_q \leq H
• 1 \leq C_q \leq W
• All input values are integers.

Sample Input 1

2 4 3
1 2
1 2
1 3

Sample Output 1

2

The process of handling the queries can be explained as follows:

• In the 1st query, (R_1, C_1) = (1, 2). There is a wall at (1, 2), so the wall at (1, 2) is destroyed.
• In the 2nd query, (R_2, C_2) = (1, 2). There is no wall at (1, 2), so the walls at (2,2),(1,1),(1,3), which are the first walls that appear when looking up, down, left, and right from (1, 2), are destroyed.
• In the 3rd query, (R_3, C_3) = (1, 3). There is no wall at (1, 3), so the walls at (2,3),(1,4), which are the first walls that appear when looking up, down, left, and right from (1, 3), are destroyed.

After processing all queries, there are two remaining walls, at (2, 1) and (2, 4).

Sample Input 2

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

Sample Output 2

10

Sample Input 3

4 3 10
2 2
4 1
1 1
4 2
2 1
3 1
1 3
1 2
4 3
4 2

Sample Output 3

2

Problem Statement

A souvenir shop at AtCoder Land sells N boxes.

The boxes are numbered 1 to N, and box i has a price of A_i yen and contains A_i pieces of candy.

Takahashi wants to buy M out of the N boxes and give one box each to M people named 1, 2, \ldots, M.

Here, he wants to buy boxes that can satisfy the following condition:

• For each i = 1, 2, \ldots, M, person i is given a box containing at least B_i pieces of candy.

Note that it is not allowed to give more than one box to a single person or to give the same box to multiple people.

Determine whether it is possible to buy M boxes that can satisfy the condition, and if it is possible, find the minimum total amount of money Takahashi needs to pay.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 10^9
• All input values are integers.

Sample Input 1

4 2
3 4 5 4
1 4

Sample Output 1

7

Takahashi can buy boxes 1 and 4, and give box 1 to person 1 and box 4 to person 2 to satisfy the condition.

In this case, he needs to pay 7 yen in total, and it is impossible to satisfy the condition by paying less than 7 yen, so print 7.

Sample Input 2

3 3
1 1 1
1000000000 1000000000 1000000000

Sample Output 2

-1

Sample Input 3

7 3
2 6 8 9 5 1 11
3 5 7

Sample Output 3

19

Problem Statement

There are N houses at points (X_1,Y_1),\ldots,(X_N,Y_N) on a two-dimensional plane.

Initially, Santa Claus is at point (S_x,S_y). He will act according to the sequence (D_1,C_1),\ldots,(D_M,C_M) as follows:

• For i=1,2,\ldots,M in order, he moves as follows:
  • Let (x,y) be the point where he currently is.
    • If D_i is U, move in a straight line from (x,y) to (x,y+C_i).
    • If D_i is D, move in a straight line from (x,y) to (x,y-C_i).
    • If D_i is L, move in a straight line from (x,y) to (x-C_i,y).
    • If D_i is R, move in a straight line from (x,y) to (x+C_i,y).

Find the point where he is after completing all actions, and the number of distinct houses he passed through or arrived at during his actions. If the same house is passed multiple times, it is only counted once.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• -10^9 \leq X_i,Y_i \leq 10^9
• The pairs (X_i,Y_i) are distinct.
• -10^9 \leq S_x,S_y \leq 10^9
• There is no house at (S_x,S_y).
• Each D_i is one of U, D, L, R.
• 1 \leq C_i \leq 10^9
• All input numbers are integers.

Sample Input 1

3 4 3 2
2 2
3 3
2 1
L 2
D 1
R 1
U 2

Sample Output 1

2 3 2

Santa Claus behaves as follows:

• D_1= L, so he moves from (3,2) to (3-2,2) in a straight line. During this, he passes through the house at (2,2).
• D_2= D, so he moves from (1,2) to (1,2-1) in a straight line.
• D_3= R, so he moves from (1,1) to (1+1,1) in a straight line. During this, he passes through the house at (2,1).
• D_4= U, so he moves from (2,1) to (2,1+2) in a straight line. During this, he passes through the house at (2,2), but it has already been passed.

The number of houses he passed or arrived during his actions is 2.

Sample Input 2

1 3 0 0
1 1
R 1000000000
R 1000000000
R 1000000000

Sample Output 2

3000000000 0 0

Be careful with overflow.

Problem Statement

There is a directed graph G with N vertices and M edges. The vertices are numbered 1, 2, \ldots, N, and for each i (1 \leq i \leq M), the i-th directed edge goes from Vertex x_i to y_i. G does not contain directed cycles.

Find the length of the longest directed path in G. Here, the length of a directed path is the number of edges in it.

Constraints

• All values in input are integers.
• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq x_i, y_i \leq N
• All pairs (x_i, y_i) are distinct.
• G does not contain directed cycles.

Sample Input 1

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

Sample Output 1

3

The red directed path in the following figure is the longest:

Sample Input 2

6 3
2 3
4 5
5 6

Sample Output 2

2

The red directed path in the following figure is the longest:

Sample Input 3

5 8
5 3
2 3
2 4
5 2
5 1
1 4
4 3
1 3

Sample Output 3

3

The red directed path in the following figure is one of the longest:

Problem Statement

There are N dishes, numbered 1, 2, \ldots, N. Initially, for each i (1 \leq i \leq N), Dish i has a_i (1 \leq a_i \leq 3) pieces of sushi on it.

Taro will perform the following operation repeatedly until all the pieces of sushi are eaten:

• Roll a die that shows the numbers 1, 2, \ldots, N with equal probabilities, and let i be the outcome. If there are some pieces of sushi on Dish i, eat one of them; if there is none, do nothing.

Find the expected number of times the operation is performed before all the pieces of sushi are eaten.

Constraints

• All values in input are integers.
• 1 \leq N \leq 300
• 1 \leq a_i \leq 3

Sample Input 1

3
1 1 1

Sample Output 1

5.5

The expected number of operations before the first piece of sushi is eaten, is 1. After that, the expected number of operations before the second sushi is eaten, is 1.5. After that, the expected number of operations before the third sushi is eaten, is 3. Thus, the expected total number of operations is 1 + 1.5 + 3 = 5.5.

Sample Input 2

1
3

Sample Output 2

3

Outputs such as 3.00, 3.000000003 and 2.999999997 will also be accepted.

Sample Input 3

2
1 2

Sample Output 3

4.5

Sample Input 4

10
1 3 2 3 3 2 3 2 1 3

Sample Output 4

54.48064457488221

Problem Statement

Taro and Jiro will play the following game against each other.

Initially, they are given a sequence a = (a_1, a_2, \ldots, a_N). Until a becomes empty, the two players perform the following operation alternately, starting from Taro:

• Remove the element at the beginning or the end of a. The player earns x points, where x is the removed element.

Let X and Y be Taro's and Jiro's total score at the end of the game, respectively. Taro tries to maximize X - Y, while Jiro tries to minimize X - Y.

Assuming that the two players play optimally, find the resulting value of X - Y.

Constraints

• All values in input are integers.
• 1 \leq N \leq 3000
• 1 \leq a_i \leq 10^9

Sample Input 1

4
10 80 90 30

Sample Output 1

10

The game proceeds as follows when the two players play optimally (the element being removed is written bold):

• Taro: (10, 80, 90, 30) → (10, 80, 90)
• Jiro: (10, 80, 90) → (10, 80)
• Taro: (10, 80) → (10)
• Jiro: (10) → ()

Here, X = 30 + 80 = 110 and Y = 90 + 10 = 100.

Sample Input 2

3
10 100 10

Sample Output 2

-80

The game proceeds, for example, as follows when the two players play optimally:

• Taro: (10, 100, 10) → (100, 10)
• Jiro: (100, 10) → (10)
• Taro: (10) → ()

Here, X = 10 + 10 = 20 and Y = 100.

Sample Input 3

1
10

Sample Output 3

10

Sample Input 4

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1

Sample Output 4

4999999995

The answer may not fit into a 32-bit integer type.

Sample Input 5

6
4 2 9 7 1 5

Sample Output 5

2

The game proceeds, for example, as follows when the two players play optimally:

• Taro: (4, 2, 9, 7, 1, 5) → (4, 2, 9, 7, 1)
• Jiro: (4, 2, 9, 7, 1) → (2, 9, 7, 1)
• Taro: (2, 9, 7, 1) → (2, 9, 7)
• Jiro: (2, 9, 7) → (2, 9)
• Taro: (2, 9) → (2)
• Jiro: (2) → ()

Here, X = 5 + 1 + 9 = 15 and Y = 4 + 7 + 2 = 13.

Problem Statement

There are N products labeled 1 to N flowing on a conveyor belt. A Keyence printer is attached to the conveyor belt, and product i enters the range of the printer T_i microseconds from now and leaves it D_i microseconds later.

The Keyence printer can instantly print on one product within the range of the printer (in particular, it is possible to print at the moment the product enters or leaves the range of the printer). However, after printing once, it requires a charge time of 1 microseconds before it can print again. What is the maximum number of products the printer can print on when the product and timing for the printer to print are chosen optimally?

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq T_i,D_i \leq 10^{18}
• All input values are integers.

Sample Input 1

5
1 1
1 1
2 1
1 2
1 4

Sample Output 1

4

Below, we will simply call the moment t microseconds from now time t.

For example, you can print on four products as follows:

• Time 1 : Products 1,2,4,5 enter the range of the printer. Print on product 4.
• Time 2 : Product 3 enters the range of the printer, and products 1,2 leave the range of the printer. Print on product 1.
• Time 3 : Products 3,4 leave the range of the printer. Print on product 3.
• Time 4.5 : Print on product 5.
• Time 5 : Product 5 leaves the range of the printer.

It is impossible to print on all five products, so the answer is 4.

Sample Input 2

2
1 1
1000000000000000000 1000000000000000000

Sample Output 2

2

Sample Input 3

10
4 1
1 2
1 4
3 2
5 1
5 1
4 1
2 1
4 1
2 4

Sample Output 3

6

Problem Statement

You are given a weighted simple connected undirected graph with N vertices and M edges, where vertices are numbered 1 to N, and edges are numbered 1 to M. Additionally, a positive integer K is given.
Edge i\ (1\leq i\leq M) connects vertices u_i and v_i and has a weight of w_i.

For a spanning tree T of this graph, the cost of T is defined as the sum, modulo K, of the weights of the edges in T. Find the minimum cost of a spanning tree of this graph.

Constraints

• 2\leq N\leq8
• N-1\leq M\leq\dfrac{N(N-1)}2
• 1\leq K\leq10^{15}
• 1\leq u_i\lt v_i\leq N\ (1\leq i\leq M)
• 0\leq w_i\lt K\ (1\leq i\leq M)
• The given graph is simple and connected.
• All input values are integers.

Sample Input 1

5 6 328
1 2 99
1 3 102
2 3 86
2 4 94
2 5 95
3 4 81

Sample Output 1

33

The given graph is shown below:

The cost of the spanning tree containing edges 1,3,5,6 is (99+86+81+95)\bmod{328}=361\bmod{328}=33. The cost of every spanning tree of this graph is at least 33, so print 33.

Sample Input 2

6 5 998244353
1 2 337361568
1 6 450343304
2 3 61477244
2 5 745383438
4 5 727360840

Sample Output 2

325437688

Print the cost of the only spanning tree of this graph, which is 325437688.

Sample Input 3

8 28 936294041850197
1 2 473294720906780
1 3 743030800139244
1 4 709363019414774
1 5 383643612490312
1 6 557102781022861
1 7 623179288538138
1 8 739618599410809
2 3 857687812294404
2 4 893923168139714
2 5 581822471860662
2 6 740549363586558
2 7 307226438833222
2 8 447399029952998
3 4 636318083622768
3 5 44548707643622
3 6 307262781240755
3 7 12070267388230
3 8 700247263184082
4 5 560567890325333
4 6 704726113717147
4 7 588263818615687
4 8 549007536393172
5 6 779230871080408
5 7 825982583786498
5 8 713928998174272
6 7 751331074538826
6 8 449873635430228
7 8 11298381761479

Sample Output 3

11360716373

Note that the input and the answer may not fit into a 32\operatorname{bit} integer.

Story

AtCoder sells several limited-edition goods featuring its logo. They have now decided to launch a "Special Set," which bundles these limited-edition goods at a discounted price. Takahashi is assigned to pack the goods, which are delivered one by one on a conveyor belt, into a single cardboard box and hand it over to a delivery service. To prepare for the launch, he has decided to practice packing.

Since the shipping cost is proportional to the sum of the width and height of the cardboard box, it is necessary to make an effort to pack the goods into as small a box as possible. Each good is rectangular, but Takahashi does not have measuring tools, so he estimates the width and height by eye and consults you, an expert in optimization, over the phone.

When you instruct Takahashi on how to arrange the goods over the phone, he follows your instructions and arranges the items accordingly. He then estimates by eye the width and height of the cardboard box required for that arrangement and reports the results back to you. Based on that information, you provide new instructions for the arrangement.

Repeat this process to find an arrangement that packs all the goods into as small a cardboard box as possible.

Problem Statement

You are given N rectangles. The i-th rectangle has width w_i and height h_i. For each rectangle, observed values w'_i=\mathrm{normal}(w_i, \sigma) and h'_i=\mathrm{normal}(h_i, \sigma) are provided as input, which include measurement errors. Here, \mathrm{normal}(\mu, \sigma) is a function that generates a value through the following steps:

1. Generate a random value from a normal distribution with mean \mu and standard deviation \sigma.
2. Round the generated value to the nearest integer.
3. If the resulting value is less than 1, it is set to 1, and if it exceeds 10^9, it is set to 10^9.

Place these rectangles on a plane in the order of their indices such that they do not overlap. Each rectangle can be rotated 90^\circ, swapping its width and height if necessary.

The positive x-axis extends to the right, and the positive y-axis extends downward. Rectangles can be placed in the region where x \geq 0 and y \geq 0. You are required to specify the placement method as a sequence (p_0, r_0, d_0, b_0), (p_1, r_1, d_1, b_1), \dots, such that:

• p_i represents the index of the rectangle to be placed at the i-th step (0 \leq p_i \leq N-1). You can try placing only some of the rectangles, but the indices must be in ascending order; in other words, for all i < j, p_i < p_j must hold.
• r_i indicates whether the rectangle should be rotated by 90^\circ. If r_i = 0, the rectangle is not rotated; if r_i = 1, the rectangle is rotated.
• d_i specifies the direction in which the rectangle is placed.
  • If d_i is U, the rectangle is moved upward until it stops at the bottom edge of another rectangle that has already been placed or at the line y = 0.
  • If d_i is L, the rectangle is moved leftward until it stops at the right edge of another rectangle that has already been placed or at the line x = 0.
• b_i represents the reference rectangle for placement. b_i must be either -1 or the index of a previously placed rectangle.
  • When placing the rectangle upward (U), b_i specifies which rectangle’s right edge should align with the left edge of the new rectangle. If b_i = -1, the left edge of the rectangle aligns with x = 0.
  • When placing the rectangle leftward (L), b_i specifies which rectangle’s bottom edge should align with the top edge of the new rectangle. If b_i = -1, the top edge of the rectangle aligns with y = 0.

Example of Operations

In the following example, the third rectangle is placed without rotation, and the results of placement are illustrated for each pair of (d, b).

Operation (d,b)	Before	(U,-1)	(U,0)	(U,1)	(U,2)
Result
Operation (d,b)	Before	(L,-1)	(L,0)	(L,1)	(L,2)
Result

Repeat the following operations T times:

1. Specify how to place the rectangles. Note that placement starts from an empty state, not continuing from the previous placement.
2. After placement, let the width (the maximum x-coordinate where rectangles exist) be W, and the height (the maximum y-coordinate where rectangles exist) be H. Then, the measured values W' = \mathrm{normal}(W, \sigma) and H' = \mathrm{normal}(H, \sigma) are obtained as the results of the measurement.

Scoring

Let W_t and H_t be the width and height of the placement at the t-th turn, respectively, and let U_t be the set of rectangles that are not used in this turn. Then, the score s_t for the t-th turn is defined as follows:

\[ s_t = W_t + H_t + \sum_{i\in U_t}(w_i+h_i) \]

Then you obtain an absolute score of \min_t s_t. The lower the absolute score, the better.

For each test case, we compute the relative score \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}), where YOUR is your absolute score and MIN is the lowest absolute score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.

The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MIN calculation for those test cases.

The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.

Number of test cases

• Provisional test: 50
• System test: 3000. We will publish seeds.txt (sha256=1e93374aa02130a1167c2893f1904b4234a3b517d1e7b9d25022a9125ff3777d) after the contest is over.

About relative evaluation system

In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores.

The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.

About execution time

Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.

Input and Output

First, the number of rectangles N, the number of operation turns T, the standard deviation \sigma of the measurement error, and the measured sizes w'_i and h'_i of each rectangle are given from Standard Input in the following format.

N T \sigma
w'_0 h'_0
\vdots
w'_{N-1} h'_{N-1}

• The number of rectangles N satisfies 30 \leq N \leq 100.
• The number of operations T satisfies N/2 \leq T \leq 4N.
• The standard deviation of the measurement error \sigma is an integer satisfying 1000 \leq \sigma \leq 10000.
• The measured values of the width and height, w'_i and h'_i, are integers between 1 and 10^9 inclusive.

After reading the above information, repeat the following process T times.

Let the sequence representing the rectangle placement method be (p_0, r_0, d_0, b_0), (p_1, r_1, d_1, b_1), \dots, (p_{n-1}, r_{n-1}, d_{n-1}, b_{n-1}). Here, n represents the number of rectangles to place, and n may be less than N. Output this sequence to Standard Output in the following format.

n
p_0 r_0 d_0 b_0
\vdots 
p_{n-1} r_{n-1} d_{n-1} b_{n-1}

After the output, the measured values of the width and height, W' and H', are given from Standard Input in the following format.

W' H'

The output must be followed by a new line, and you have to flush Standard Output. Otherwise, the submission might be judged as TLE.

Your program may output comment lines starting with #. The web version of the visualizer displays the comment lines at the corresponding timing, which may be useful for debugging and analysis. Since the judge program ignores all comment lines, you can submit a program that outputs comment lines as is.

Example

4 3 1000
77685 46130
32459 75368
54192 88183
60740 42948

2
0 0 U -1
1 1 U 0

153220 47195

4
0 0 U -1
1 1 L -1
2 1 L 1
3 0 U -1

167543 86611

4
0 0 U -1
1 0 L -1
2 0 U -1
3 0 U 2

113031 134437

Show example

Sample Solution

import random

def query(prdb):
    print(len(prdb))
    for p, r, d, b in prdb:
        print(p, r, d, b)
    W, H = map(int, input().split())
    return W, H

N, T, sigma = map(int, input().split())
wh = [tuple(map(int, input().split())) for _ in range(N)]

rng = random.Random(1234)

for _ in range(T):
    prdb = []
    for i in range(N):
        prdb.append((
            i,
            rng.randint(0, 1),
            ['U', 'L'][rng.randint(0, 1)],
            rng.randint(-1, i - 1),
        ))
    query(prdb)

Input Generation

• \mathrm{rand}(L,U): Generates an integer uniformly at random between L and U, inclusive.
• \mathrm{rand\_double}(L,U): Generates a real number uniformly at random between L and U, inclusive.

Generation of N, T, and \sigma

• N = \mathrm{rand}(30, 100)
• T = \mathrm{round}(N \times 2^{\mathrm{rand\_double}(-1, 2)})
• \sigma = \mathrm{rand}(1000, 10000)

Generation of w and h

Let U = 10^5, and generate L = \mathrm{rand}(U/10, U/2).
For each i, w_i = \mathrm{rand}(L, U) and h_i = \mathrm{rand}(L, U) are generated.

Tools (Input generator, local tester, and visualizer)

• Web version: This is more powerful than the local version providing animations.
• Local version: You need a compilation environment of Rust language.
  • Pre-compiled binary for Windows: If you are not familiar with the Rust language environment, please use this instead.

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.

Specification of input files used by the tools

The input file provided to the local tester includes additional information in the following format appended to the end of the prior-information given to the solution program.

w_0 h_0
\vdots
w_{N-1} h_{N-1}
dW_0 dH_0
\vdots
dW_{T-1} dH_{T-1}

• w_i and h_i represent the true width and height of the i-th rectangle.
• dW_t and dH_t are the measurement errors added to the results of the t-th turn.