Problem Statement

A function f(x) defined for non-negative integer x satisfies the following conditions:

• f(0) = 1;
• f(k) = k \times f(k-1) for all positive integers k.

Find f(N).

Constraints

• N is an integer such that 0 \le N \le 10.

Sample Input 1

2

Sample Output 1

2

We have f(2) = 2 \times f(1) = 2 \times 1 \times f(0) = 2 \times 1 \times 1 = 2.

Sample Input 2

3

Sample Output 2

6

We have f(3) = 3 \times f(2) = 3 \times 2 = 6.

Sample Input 3

0

Sample Output 3

1

Sample Input 4

10

Sample Output 4

3628800

Problem Statement

Given a non-negative integer X, perform the following operation for i=1,2,\dots,K in this order and find the resulting X.

• Round X off to the nearest 10^i.
  • Formally, replace X with Y that is "the largest multiple of 10^i that minimizes |Y-X|."
  • Here are some examples:
    • Rounding 273 off to the nearest 10^2 yields 300.
    • Rounding 999 off to the nearest 10^3 yields 1000.
    • Rounding 100 off to the nearest 10^{10} yields 0.
    • Rounding 1015 off to the nearest 10^1 yields 1020.

Constraints

• X and K are integers.
• 0 \le X < 10^{15}
• 1 \le K \le 15

Sample Input 1

2048 2

Sample Output 1

2100

X changes as 2048 \rightarrow 2050 \rightarrow 2100 by the operations.

Sample Input 2

1 15

Sample Output 2

0

Sample Input 3

999 3

Sample Output 3

1000

Sample Input 4

314159265358979 12

Sample Output 4

314000000000000

X may not fit into a 32-bit integer type.

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. For each K = 0, 1, 2, \ldots, N-1, solve the following problem.

Find the number of integers i between 1 and N (inclusive) such that:

• A contains exactly K distinct integers greater than A_i.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
2 7 1 8 2 8

Sample Output 1

2
1
2
1
0
0

For example, we will find the answer for K=2.

• Regarding A_1 = 2, A contains 2 distinct integers greater than A_1: 7 and 8.
• Regarding A_2 = 7, A contains 1 distinct integer greater than A_2: 8.
• Regarding A_3 = 1, A contains 3 distinct integers greater than A_3: 2, 7, and 8.
• Regarding A_4 = 8, A contains 0 distinct integers greater than A_4 (there is no such integer).
• Regarding A_5 = 2, A contains 2 distinct integers greater than A_5: 7 and 8.
• Regarding A_6 = 8, A contains 0 distinct integers greater than A_6 (there is no such integer).

Thus, there are two i's, i = 1 and i = 5, such that A contains exactly K = 2 distinct integers greater than A_i. Therefore, the answer for K = 2 is 2.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

Sample Output 3

2
1
2
1
2
1
1
0
0
0

Problem Statement

There is 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.
N squares, (r_1, c_1), (r_2, c_2), \ldots, (r_N, c_N), have walls.

Takahashi is initially at square (r_\mathrm{s}, c_\mathrm{s}).

Q instructions are given to Takahashi. For i = 1, 2, \ldots, Q, the i-th instruction is represented by a pair of a character d_i and a positive integer l_i. d_i is one of L, R, U, and D, representing the directions of left, right, up, and down, respectively.

Given the i-th direction, Takahashi repeats the following action l_i times:

If a square without a wall is adjacent to the current square in the direction represented by d_i, move to that square; otherwise, do nothing.

For i = 1, 2, \ldots, Q, print the square where Takahashi will be after he follows the first i instructions.

Constraints

• 2 \leq H, W \leq 10^9
• 1 \leq r_\mathrm{s} \leq H
• 1 \leq c_\mathrm{s} \leq W
• 0 \leq N \leq 2 \times 10^5
• 1 \leq r_i \leq H
• 1 \leq c_i \leq W
• i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)
• (r_\mathrm{s}, c_\mathrm{s}) \neq (r_i, c_i) for all i = 1, 2, \ldots, N.
• 1 \leq Q \leq 2 \times 10^5
• d_i is one of the characters L, R, U, and D.
• 1 \leq l_i \leq 10^9
• All values in the input other than d_i are integers.

Sample Input 1

5 5 4 4
3
5 3
2 2
1 4
4
L 2
U 3
L 2
R 4

Sample Output 1

4 2
3 2
3 1
3 5

The given grid and the initial position of Takahashi are as follows, where # denotes a square with a wall, T a square where Takahashi is, and . the other squares:

...#.
.#...
.....
...T.
..#..

Given the 1-st instruction, Takahashi moves 2 squares to the left, ending up in square (4, 2) as follows:

...#.
.#...
.....
.T...
..#..

Given the 2-nd instruction, Takahashi first moves 1 square upward, then he "does nothing" twice because the adjacent square in his direction has a wall. As a result, he ends up in square (3, 2) as follows:

...#.
.#...
.T...
.....
..#..

Given the 3-rd instruction, Takahashi first moves 1 square to the left, then he "does nothing" once because there is no square in his direction. As a result, he ends up in square (3, 1) as follows:

...#.
.#...
T....
.....
..#..

Given the 4-th instruction, Takahashi moves 4 squares to the right, ending up in square (3, 5) as follows:

...#.
.#...
....T
.....
..#..

Sample Input 2

6 6 6 3
7
3 1
4 3
2 6
3 4
5 5
1 1
3 2
10
D 3
U 3
L 2
D 2
U 3
D 3
U 3
R 3
L 3
D 1

Sample Output 2

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

Problem Statement

We have an integer sequence A and a notebook. The notebook has 10^9 pages.

You are given Q queries. Each query is of one of the following four kinds:

ADD x: append an integer x to the tail of A.

DELETE: remove the last term of A if A is not empty; do nothing otherwise.

SAVE y: erase the sequence recorded on the y-th page of the notebook, and record the current A onto the y-th page.

LOAD z: replace A with the sequence recorded on the z-th page of the notebook.

Initially, A is an empty sequence, and an empty sequence is recorded on each page of the notebook. Process Q queries successively in the given order and print the last term of A after processing each query.

The use of fast input and output methods is recommended because of potentially large input and output.

Constraints

• 1 \leq Q \leq 5 \times 10^5
• 1 \leq x, y, z \leq 10^9
• Q, x, y, and z are integers.
• Each of the given queries is of one of the four kinds in the Problem Statement.

Sample Input 1

11
ADD 3
SAVE 1
ADD 4
SAVE 2
LOAD 1
DELETE
DELETE
LOAD 2
SAVE 1
LOAD 3
LOAD 1

Sample Output 1

3 3 4 4 3 -1 -1 4 4 -1 4

Initially, A is an empty sequence, so A = (), and an empty sequence is recorded on each page of the notebook.

• By the 1-st query, 3 is appended to the tail of A, resulting in A = (3).
• By the 2-nd query, the sequence recorded on the 1-st page of the notebook becomes (3). It remains that A = (3).
• By the 3-rd query, 4 is appended to the tail of A, resulting in A = (3, 4).
• By the 4-th query, the sequence recorded on the 2-nd page of the notebook becomes (3, 4). It remains that A = (3, 4).
• By the 5-th query, A is replaced by (3), which is recorded on the 1-st page of the notebook, resulting in A = (3).
• By the 6-th query, the last term of A is removed, resulting in A = ().
• By the 7-th query, nothing happens because A is already empty. It remains that A = ().
• By the 8-th query, A is replaced by (3,4), which is recorded on the 2-nd page of the notebook, resulting in A = (3, 4).
• By the 9-th query, the sequence recorded on the 1-st page of the notebook becomes (3, 4). It remains that A = (3, 4).
• By the 10-th query, A is replaced by (), which is recorded on the 3-rd page of the notebook, resulting in A = ().
• By the 11-th query, A is replaced by (3, 4), which is recorded on the 1-st page of the notebook, resulting in A = (3, 4).

Sample Input 2

21
ADD 4
ADD 3
DELETE
ADD 10
LOAD 7
SAVE 5
SAVE 5
ADD 4
ADD 4
ADD 5
SAVE 5
ADD 2
DELETE
ADD 1
SAVE 5
ADD 7
ADD 8
DELETE
ADD 4
DELETE
LOAD 5

Sample Output 2

4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1

Problem Statement

Takahashi is at the origin of a number line. Takahashi wants to reach the goal at coordinate X.

Also, there are N walls and N hammers on the number line.

• At coordinates Y_1,Y_2,\dots,Y_N are walls of types 1,2,\dots,N, respectively.
  • Initially, Takahashi cannot get over the walls.
• At coordinates Z_1,Z_2,\dots,Z_N are hammers of types 1,2,\dots,N, respectively.
  • When he arrives at a coordinate with a hammer, he obtains the hammer.
  • The hammer of type i is dedicated to destroying the wall of type i. After he obtains the hammer of type i, he can destroy the wall of type i and get over it.

Determine if he can reach the goal. If he can, find the minimum distance he travels.

Constraints

• All values in the input are integers.
• 1 \le N \le 1500
• 1 \le |X|,|Y_i|,|Z_i| \le 10^9
• The (2 \times N + 1) coordinates X,Y_i and Z_i are distinct.

Sample Input 1

3 10
-2 8 -5
5 -10 3

Sample Output 1

40

Takahashi can reach the goal by traveling a distance of 40 as follows, which is the minimum possible:

• He starts at coordinate 0.
• He moves to coordinate 3 to obtain the hammer of type 3.
• He moves to coordinate 5 to obtain the hammer of type 1.
• He moves to coordinate -2 to destroy the wall of type 1.
• He moves to coordinate -5 to destroy the wall of type 3.
• He moves to coordinate -10 to obtain the hammer of type 2.
• He moves to coordinate 8 to destroy the wall of type 2.
• He moves to coordinate 10, which is the goal.

Sample Input 2

5 -1
10 -20 30 -40 50
-10 20 -30 40 -50

Sample Output 2

1

It may not be required that he obtains a hammer or destroys a wall to reach the goal.

Sample Input 3

1 100
30
60

Sample Output 3

-1

Takahashi cannot obtain the hammer of type 1, and neither can he reach the goal.

Sample Input 4

4 865942261
703164879 -531670946 -874856231 -700164975
-941120316 599462305 -649785130 665402307

Sample Output 4

4078987507

Problem Statement

Find the number, modulo 998244353, of square matrices of size N whose elements are non-negative integers, that satisfy both of the following two conditions:

• for all i = 1, 2, \ldots, N, the sum of the elements in the i-th row is R_i;
• for all i = 1, 2, \ldots, N, the sum of the elements in the i-th column is C_i.

Note that R_i and C_i given in the input are integers between 0 and 2 (see Constraints).

Constraints

• 1 \leq N \leq 5000
• 0 \leq R_i \leq 2
• 0 \leq C_i \leq 2
• All values in the input are integers.

Sample Input 1

3
1 1 1
0 1 2

Sample Output 1

3

The following 3 matrices satisfy the conditions:

0 1 0
0 0 1
0 0 1

0 0 1
0 1 0
0 0 1

0 0 1
0 0 1
0 1 0

Sample Input 2

3
1 1 1
2 2 2

Sample Output 2

0

Sample Input 3

18
2 0 1 2 0 1 1 2 1 1 2 0 1 2 2 1 0 0
1 1 0 1 1 1 1 1 1 1 1 1 2 1 1 0 2 2

Sample Output 3

968235177

Be sure to print the count modulo 998244353.

Problem Statement

We have a sequence A consisting of integer pairs. Initially, A = ( (0, 1), (1, 0) ).

You may perform the following operation on A as many (possibly zero) times as you want:

• choose adjacent two integer pairs (a, b) and (c, d), and insert (a + c, b + d) between them.

For a sequence T consisting of integer pairs, let us define f(T) as follows:

• let f(T) = (the minimum number of operations required to make every element of T contained in A).
  • We say that "every element of T is contained in A" if, for all elements x contained in T, x is contained in (the set consisting of the elements contained in A).
• Here, if there are no such operations, let f(T) = 0.

There is a sequence S = ((a_1, b_1), (a_2, b_2), \dots, (a_N, b_N)) consisting of N integer pairs. Here, all elements of S are pairwise distinct.
There are \frac{N \times (N+1)}{2} possible consecutive subarrays S_{l,r}=((a_l,b_l),(a_{l+1},b_{l+1}),\dots,(a_r,b_r)) of S. Find the sum, modulo 998244353, of f(S_{l,r}) over those subarrays.
Formally, find \displaystyle \sum^{N} _ {l=1} \sum^{N} _ {r=l} f(S_{l,r}), modulo 998244353.

Constraints

• 1 \le N \le 10^5
• 0 \le a_i,b_i \le 10^9
• a_i \neq a_j or b_i \neq b_j, if i \neq j.

Sample Input 1

7
1 2
3 7
3 5
0 0
1000000000 1
0 1
6 3

Sample Output 1

3511324

• f(S_{1,1})=2.
  • We can make ((0,1),(1,0)) \rightarrow ((0,1),(1,1),(1,0)) \rightarrow ((0,1),(1,2),(1,1),(1,0)).
• f(S_{1,2})=5.
• f(S_{1,3})=7.
• f(S_{2,2})=5.
• f(S_{2,3})=7.
• f(S_{3,3})=4.
• f(S_{5,5})=1000000000 = 10^9.
• f(S_{5,6})=1000000000 = 10^9.
• f(S_{6,6})=0.
  • (0, 1) is originally contained in A.
• f(S_{l,r})=0 for all S_{l,r} not mentioned above.
  • We can prove that A can never contain (0,0) or (6,3) regardless of operations.

Therefore, the sum of f(S_{l,r}) is 2000000030 = 2 \times 10^9 + 30, whose remainder when divided by 998244353 is 3511324.