Problem Statement

A fruit store sells apples.
You may perform the following operations as many times as you want in any order:

• Buy one apple for X yen (the currency in Japan).
• Buy three apples for Y yen.

How much yen do you need to pay to obtain exactly N apples?

Constraints

• 1 \leq X \leq Y \leq 100
• 1 \leq N \leq 100
• All values in input are integers.

Sample Input 1

10 25 10

Sample Output 1

85

Buy three apples for 25 yen three times and one apple for 10 yen, and you will obtain exactly 10 apples for a total of 85 yen.
You cannot obtain exactly 10 apples for a lower cost, so the answer is 85 yen.

Sample Input 2

10 40 10

Sample Output 2

100

It is optimal to buy an apple for 10 yen 10 times.

Sample Input 3

100 100 2

Sample Output 3

200

The only way to obtain exactly 2 apples is to buy an apple for 100 yen twice.

Sample Input 4

100 100 100

Sample Output 4

3400

Problem Statement

Takahashi is exploring a cave in a video game.

The cave consists of N rooms arranged in a row. The rooms are numbered Room 1,2,\ldots,N from the entrance.

Takahashi is initially in Room 1, and the time limit is T.
For each 1 \leq i \leq N-1, he may consume a time of A_i to move from Room i to Room (i+1). There is no other way to move between rooms. He cannot make a move that makes the time limit 0 or less.

There are M bonus rooms in the cave. The i-th bonus room is Room X_i; when he arrives at the room, the time limit increases by Y_i.

Can Takahashi reach Room N?

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq N-2
• 1 \leq T \leq 10^9
• 1 \leq A_i \leq 10^9
• 1 < X_1 < \ldots < X_M < N
• 1 \leq Y_i \leq 10^9
• All values in input are integers.

Sample Input 1

4 1 10
5 7 5
2 10

Sample Output 1

Yes

• Takahashi is initially in Room 1, and the time limit is 10.
• He consumes a time of 5 to move to Room 2. Now the time limit is 5. Then, the time limit increases by 10; it is now 15.
• He consumes a time of 7 to move to Room 3. Now the time limit is 8.
• He consumes a time of 5 to move to Room 4. Now the time limit is 3.

Sample Input 2

4 1 10
10 7 5
2 10

Sample Output 2

No

He cannot move from Room 1 to Room 2.

Problem Statement

We have a grid with H horizontal rows and W vertical columns. (i, j) denotes the square at the i-th row from the top and j-th column from the left.
(i,j) has a character G_{i,j} written on it. G_{i,j} is U, D, L, or R.

You are initially at (1,1). You repeat the following operation until you cannot make a move.

Let (i,j) be the square you are currently at.
If G_{i,j} is U and i \neq 1, move to (i-1,j).
If G_{i,j} is D and i \neq H, move to (i+1,j).
If G_{i,j} is L and j \neq 1, move to (i,j-1).
If G_{i,j} is R and j \neq W, move to (i,j+1).
Otherwise, you cannot make a move.

Print the square you end up at when you cannot make a move.
If you indefinitely repeat moving, print -1 instead.

Constraints

• 1 \leq H, W \leq 500
• G_{i,j} is U, D, L, or R.
• H and W are integers.

Sample Input 1

2 3
RDU
LRU

Sample Output 1

1 3

You will move as (1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3), ending up here, so the answer is (1, 3).

Sample Input 2

2 3
RRD
ULL

Sample Output 2

-1

You will indefinitely repeat moving as (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (1, 1) \to (1, 2) \to \dots, so -1 should be printed in this case.

Sample Input 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

Sample Output 3

9 5

Problem Statement

There is a sequence A=(A_0,\ldots,A_{N-1}) of length N.
Determine if there exists a tuple of integers (x,y,z,w) that satisfies all of the following conditions:

• 0 \leq x < y < z < w \leq N
• A_x + A_{x+1} + \ldots + A_{y-1} = P
• A_y + A_{y+1} + \ldots + A_{z-1} = Q
• A_z + A_{z+1} + \ldots + A_{w-1} = R

Constraints

• 3 \leq N \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq P,Q,R \leq 10^{15}
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes

(x,y,z,w)=(1,3,6,8) satisfies the conditions.

Sample Input 2

9 100 101 100
31 41 59 26 53 58 97 93 23

Sample Output 2

No

Sample Input 3

7 1 1 1
1 1 1 1 1 1 1

Sample Output 3

Yes

Problem Statement

Takahashi is at the origin of a two-dimensional plane.
Takahashi will repeat teleporting N times. In each teleportation, he makes one of the following moves:

• Move from the current coordinates (x,y) to (x+A,y+B)
• Move from the current coordinates (x,y) to (x+C,y+D)
• Move from the current coordinates (x,y) to (x+E,y+F)

There are obstacles on M points (X_1,Y_1),\ldots,(X_M,Y_M) on the plane; he cannot teleport to these coordinates.

How many paths are there resulting from the N teleportations? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 300
• 0 \leq M \leq 10^5
• -10^9 \leq A,B,C,D,E,F \leq 10^9
• (A,B), (C,D), and (E,F) are distinct.
• -10^9 \leq X_i,Y_i \leq 10^9
• (X_i,Y_i)\neq(0,0)
• (X_i,Y_i) are distinct.
• All values in input are integers.

Sample Input 1

2 2
1 1 1 2 1 3
1 2
2 2

Sample Output 1

5

The following 5 paths are possible:

• (0,0)\to(1,1)\to(2,3)
• (0,0)\to(1,1)\to(2,4)
• (0,0)\to(1,3)\to(2,4)
• (0,0)\to(1,3)\to(2,5)
• (0,0)\to(1,3)\to(2,6)

Sample Input 2

10 3
-1000000000 -1000000000 1000000000 1000000000 -1000000000 1000000000
-1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000

Sample Output 2

0

Sample Input 3

300 0
0 0 1 0 0 1

Sample Output 3

292172978

Problem Statement

In an N-dimensional space, the Manhattan distance d(x,y) between two points x=(x_1, x_2, \dots, x_N) and y = (y_1, y_2, \dots, y_N) is defined by:

A point x=(x_1, x_2, \dots, x_N) is said to be a lattice point if the components x_1, x_2, \dots, x_N are all integers.

You are given lattice points p=(p_1, p_2, \dots, p_N) and q = (q_1, q_2, \dots, q_N) in an N-dimensional space.
How many lattice points r satisfy d(p,r) \leq D and d(q,r) \leq D? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 100
• 0 \leq D \leq 1000
• -1000 \leq p_i, q_i \leq 1000
• All values in input are integers.

Sample Input 1

1 5
0
3

Sample Output 1

8

When N=1, we consider points in a one-dimensional space, that is, on a number line.
8 lattice points satisfy the conditions: -2,-1,0,1,2,3,4,5.

Sample Input 2

3 10
2 6 5
2 1 2

Sample Output 2

632

Sample Input 3

10 100
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8

Sample Output 3

145428186

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N. Each element is 0, 1, or 2.
Process Q queries in order. Each query is of one of the following kinds:

• 1 L R: print the inversion number of the sequence (A_L,\ldots,A_R).
• 2 L R S T U: for each i such that L\leq i \leq R, if A_i is 0, replace it with S; if A_i is 1, replace it with T; if A_i is 2, replace it with U.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq A_i \leq 2
• 1\leq Q\leq 10^5
• In each query, 1\leq L \leq R \leq N.
• In each query of the second kind, 0\leq S,T,U \leq 2.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

3
4

Initially, A=(2,0,2,1,0).

• In the 1-st query, print the inversion number 3 of (A_2,A_3,A_4,A_5)=(0,2,1,0).
• The 2-nd query makes A=(2,2,0,1,0).
• In the 3-rd query, print the inversion number 4 of (A_2,A_3,A_4,A_5)=(2,0,1,0).

Sample Input 2

3 3
0 1 2
1 1 1
2 1 3 0 0 0
1 1 3

Sample Output 2

0
0

Problem Statement

There is a grid with H horizontal rows and W vertical columns, and (2 \times H) pieces. We consider the following game using them.
Two players take alternating turns. The game progresses as follows.

• In the initial state, every row contains one piece of the first player facing left and one piece of the second player facing right.
• The two players alternately advance one of their pieces.
• The player who is first to be unable to make a move loses, and the other player wins.

Let (i, j) denote the square at the i-th row from the top and j-th column from the left. The following moves are allowed:

• The first player can move a piece at (i,j) to (i,k) if k \lt j and none of (i,k),(i,k+1),\dots,(i,j-1) contains a piece of either player.
• The second player can move a piece at (i,j) to (i,k) if k \gt j and none of (i,j+1),(i,j+2),\dots,(i,k) contains a piece of either player.

For example, in the figure below, on a 3\times 9 grid, the first player's pieces are at (1,7),(2,1),(3,4), and the second player's pieces are at (1,3),(2,7),(3,5).
The first player can move the piece at (1,7) to (1,4),(1,5), or (1,6), and the piece at (3,4) to (3,1),(3,2), or (3,3). The first player cannot move the piece at (2,1).

Currently, there is no piece on the grid. There are \left\lbrace W(W-1)\right\rbrace^H ways to place one piece of the first player and one piece of the second player in each row, so that no two pieces are placed at the same square. How many of them satisfy the following condition? Find the count modulo 998244353.

• When they play the game optimally from that initial state, the first player wins.

Constraints

• 1 \leq H \leq 8000
• 2 \leq W \leq 30
• H and W are integers.

Sample Input 1

1 3

Sample Output 1

2

The first player can win if:

• the first player's piece is placed at (1, 3), and the second player's piece is placed at (1, 1); or
• the first player's piece is placed at (1, 2), and the second player's piece is placed at (1, 3).

Sample Input 2

9 9

Sample Output 2

583962987

Sample Input 3

265 30

Sample Output 3

366114675