Problem Statement

Takahashi is in a building with 100 floors.

He uses the stairs for moving up two floors or less or moving down three floors or less, and uses the elevator otherwise.

Does he use the stairs to move from floor X to floor Y?

Constraints

• 1 \leq X,Y \leq 100
• X \neq Y
• All input values are integers.

Sample Input 1

1 4

Sample Output 1

No

The move from floor 1 to floor 4 involves going up three floors, so Takahashi uses the elevator.

Sample Input 2

99 96

Sample Output 2

Yes

The move from floor 99 to floor 96 involves going down three floors, so Takahashi uses the stairs.

Sample Input 3

100 1

Sample Output 3

No

Problem Statement

A 326-like number is a three-digit positive integer where the product of the hundreds and tens digits equals the ones digit.

For example, 326,400,144 are 326-like numbers, while 623,777,429 are not.

Given an integer N, find the smallest 326-like number greater than or equal to N. It always exists under the constraints.

Constraints

• 100 \leq N \leq 919
• N is an integer.

Sample Input 1

320

Sample Output 1

326

320,321,322,323,324,325 are not 326-like numbers, while 326 is a 326-like number.

Sample Input 2

144

Sample Output 2

144

144 is a 326-like number.

Sample Input 3

516

Sample Output 3

600

Problem Statement

Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.

You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.

• First, choose one real number x.
• Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.

What is the maximum number of gifts you can acquire?

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le M \le 10^9
• 0 \le A_i \le 10^9

Sample Input 1

8 6
2 3 5 7 11 13 17 19

Sample Output 1

4

For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.

Sample Input 2

10 1
3 1 4 1 5 9 2 6 5 3

Sample Output 2

2

There may be multiple gifts at the same coordinate.

Sample Input 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

Sample Output 3

7

Problem Statement

You are given an integer N and strings R and C of length N consisting of A, B, and C. Solve the following problem.

There is a N \times N grid. All cells are initially empty.
You can write at most one character from A, B, and C in each cell. (You can also leave the cell empty.)

Determine if it is possible to satisfy all of the following conditions, and if it is possible, print one way to do so.

• Each row and each column contain exactly one A, one B, and one C.
• The leftmost character written in the i-th row matches the i-th character of R.
• The topmost character written in the i-th column matches the i-th character of C.

Constraints

• N is an integer between 3 and 5, inclusive.
• R and C are strings of length N consisting of A, B, and C.

Sample Input 1

5
ABCBC
ACAAB

Sample Output 1

Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA

The grid in the output example satisfies all the following conditions, so it will be treated as correct.

• Each row contains exactly one A, one B, and one C.
• Each column contains exactly one A, one B, and one C.
• The leftmost characters written in the rows are A, B, C, B, C from top to bottom.
• The topmost characters written in the columns are A, C, A, A, B from left to right.

Sample Input 2

3
AAA
BBB

Sample Output 2

No

For this input, there is no way to fill the grid to satisfy the conditions.

Problem Statement

Aoki, an employee at AtCoder Inc., has his salary for this month determined by an integer N and a sequence A of length N as follows.
First, he is given an N-sided die (dice) that shows the integers from 1 to N with equal probability, and a variable x=0.

Then, the following steps are repeated until terminated.

• Roll the die once and let y be the result.
  • If x<y, pay him A_y yen and let x=y.
  • Otherwise, terminate the process.

Aoki's salary for this month is the total amount paid through this process.
Find the expected value of Aoki's salary this month, modulo 998244353.

Constraints

• All inputs are integers.
• 1 \le N \le 3 \times 10^5
• 0 \le A_i < 998244353

Sample Input 1

3
3 2 6

Sample Output 1

776412280

Here is an example of how the process goes.

• Initially, x=0.
• Roll the die once, and it shows 1. Since 0<1, pay him A_1 = 3 yen and let x=1.
• Roll the die once, and it shows 3. Since 1<3, pay him A_3 = 6 yen and let x=3.
• Roll the die once, and it shows 1. Since 3 \ge 1, terminate the process.

In this case, his salary for this month is 9 yen.

It can be calculated that the expected value of his salary this month is \frac{49}{9} yen, whose representation modulo 998244353 is 776412280.

Sample Input 2

1
998244352

Sample Output 2

998244352

Sample Input 3

9
3 14 159 2653 58979 323846 2643383 27950288 419716939

Sample Output 3

545252774

Problem Statement

A robot is at the origin of a coordinate plane where the positive x-axis points to the right and the positive y-axis points upwards. Initially, the robot is facing the positive x-direction.

You will perform the following operation for i=1,\ldots,N in this order.

• Rotate the robot 90 degrees clockwise or counterclockwise. Then, the robot moves forward A_i units in the direction it is facing.

Can the direction of rotation be chosen so that the robot will be at the coordinates (X,Y) after the N operations?

If it is possible, determine which direction, clockwise or counterclockwise, should be chosen for each operation.

Constraints

• 1 \leq N \leq 80
• 1 \leq A_i \leq 10^7
• -10^9\leq X,Y \leq 10^9
• All input values are integers.

Sample Input 1

3 -2 4
3 2 1

Sample Output 1

Yes
LLR

Initially, the robot is at (0,0) and facing the positive x-direction. The following choices can put the robot at the coordinates (X,Y) after the N operations.

• First operation: Rotate the robot 90 degrees counterclockwise to face the positive y-direction. The robot moves forward A_1=3 units in the direction it is facing, and moves to (0,3).
• Second operation: Rotate the robot 90 degrees counterclockwise to face the negative x-direction. The robot moves forward A_2=2 units in the direction it is facing, and moves to (-2,3).
• Third operation: Rotate the robot 90 degrees clockwise to face the positive y-direction. The robot moves forward A_3=1 unit in the direction it is facing, and moves to (-2,4).

Sample Input 2

1 0 0
1

Sample Output 2

No

Sample Input 3

4 0 0
1 1 1 1

Sample Output 3

Yes
LRRR

Outputs such as LLLL and RRRR are also accepted.

Sample Input 4

14 2543269 -1705099
3 14 159 2653 58979 323846 2643383 2795028 841971 69399 37510 58 20 9

Sample Output 4

Yes
LLLLLLLLLRLRRR

Problem Statement

There are N skills numbered 1 to N and M achievements numbered 1 to M.

Each skill has a positive integer level, and the initial level of every skill is 1.

You can pay a cost of C_i yen to increase the level of skill i by 1. You can do this as many times as you want.

Achievement i is achieved when the following condition is satisfied for every j=1,\ldots,N, for which you will receive a reward of A_i yen.

• Condition: The level of skill j is at least L_{i,j}.

Find the maximum possible total reward obtained minus the total cost required when appropriately choosing how to raise the skill levels.

Constraints

• 1 \leq N,M \leq 50
• 1 \leq L_{i,j} \leq 5
• 1 \leq A_i,C_i \leq 10^6
• All input values are integers.

Sample Input 1

2 2
10 20
100 50
3 1
1 4

Sample Output 1

80

There are two skills. It costs 10 yen to raise the level of skill 1 and 20 yen to raise the level of skill 2.
There are two achievements. Achievement 1 is achieved when skill 1 is at least level 3 and skill 2 is at least level 1, for which you will receive 100 yen. Achievement 2 is achieved when skill 1 is at least 1 and skill 2 is at least level 4, for which you will receive 50 yen.

By raising skill 1 to level 3 and skill 2 to level 1, you will receive the reward of 100 yen for the cost of 20 yen, and the balance is 80 yen.

Sample Input 2

2 2
10 20
100 50
3 2
1 4

Sample Output 2

70

By raising skill 1 to level 3 and skill 2 to level 4, you will receive the reward of 150 yen for the cost of 80 yen, and the balance is 70 yen.

Sample Input 3

10 10
10922 23173 32300 22555 29525 16786 3135 17046 11245 20310
177874 168698 202247 31339 10336 14825 56835 6497 12440 110702
2 1 4 1 3 4 4 5 1 4
2 3 4 4 5 3 5 5 2 3
2 3 5 1 4 2 2 2 2 5
3 5 5 3 5 2 2 1 5 4
3 1 1 4 4 1 1 5 3 1
1 2 3 2 4 2 4 3 3 1
4 4 4 2 5 1 4 2 2 2
5 3 1 2 3 4 2 5 2 2
5 4 3 4 3 1 5 1 5 4
2 3 2 5 2 3 1 2 2 4

Sample Output 3

66900