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.

Cell (i, j) is empty if C_{i, j} is ., and not empty if C_{i, j} is #.

Takahashi is currently at cell (S_i, S_j), and he will act according to the following rules for i = 1, 2, \ldots, |X| in order.

• If the i-th character of X is L, and the cell to the left of his current cell exists and is empty, he moves to the cell to the left. Otherwise, he stays in the current cell.
• If the i-th character of X is R, and the cell to the right of his current cell exists and is empty, he moves to the cell to the right. Otherwise, he stays in the current cell.
• If the i-th character of X is U, and the cell above his current cell exists and is empty, he moves to the cell above. Otherwise, he stays in the current cell.
• If the i-th character of X is D, and the cell below his current cell exists and is empty, he moves to the cell below. Otherwise, he stays in the current cell.

Print the cell where he is after completing the series of actions.

Constraints

• 1 \leq H, W \leq 50
• 1 \leq S_i \leq H
• 1 \leq S_j \leq W
• H, W, S_i, S_j are integers.
• C_{i, j} is . or #.
• C_{S_i, S_j} = .
• X is a string of length between 1 and 50, inclusive, consisting of L, R, U, D.

Sample Input 1

2 3
2 1
.#.
...
ULDRU

Sample Output 1

2 2

Takahashi starts at cell (2, 1). His series of actions are as follows:

• The 1st character of X is U, and the cell above (2, 1) exists and is an empty cell, so he moves to the cell above, which is (1, 1).
• The 2nd character of X is L, and the cell to the left of (1, 1) does not exist, so he stays at (1, 1).
• The 3rd character of X is D, and the cell below (1, 1) exists and is an empty cell, so he moves to the cell below, which is (2, 1).
• The 4th character of X is R, and the cell to the right of (2, 1) exists and is an empty cell, so he moves to the cell to the right, which is (2, 2).
• The 5th character of X is U, and the cell above (2, 2) exists but is not an empty cell, so he stays at (2, 2).

Therefore, after completing the series of actions, he is at cell (2, 2).

Sample Input 2

4 4
4 2
....
.#..
...#
....
DUUUURULRD

Sample Output 2

2 4

Sample Input 3

6 6
1 1
.#####
######
######
######
######
######
RURLDLULLRULRDL

Sample Output 3

1 1

Problem Statement

Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.

• For each i (0\leq i \leq N-1), the length of A_i is i+1.
• For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
  • a_{i,j}=1, if j=0 or j=i.
  • a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.

Constraints

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

Sample Input 1

3

Sample Output 1

1
1 1
1 2 1

Sample Input 2

10

Sample Output 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Problem Statement

For an integer sequence A = (A_1, A_2, \ldots, A_{|A|}), we say that A is tilde-shaped if it satisfies all of the following four conditions:

• The length |A| is at least 4.
• A_1 < A_2.
• There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} < A_i > A_{i+1}.
• There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} > A_i < A_{i+1}.

You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N). Find the number of (contiguous) subarrays of P that are tilde-shaped.

Constraints

• 4 \leq N \leq 3 \times 10^5
• P = (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
• All input values are integers.

Sample Input 1

6
1 3 6 4 2 5

Sample Output 1

2

Among the subarrays of (1, 3, 6, 4, 2, 5), exactly two are tilde-shaped: (3, 6, 4, 2, 5) and (1, 3, 6, 4, 2, 5).

Sample Input 2

6
1 2 3 4 5 6

Sample Output 2

0

Sample Input 3

12
11 3 8 9 5 2 10 4 1 6 12 7

Sample Output 3

4

Problem Statement

There are N boxes numbered 1 to N and N items numbered 1 to N. Item i (1 \leq i \leq N) is in box A_i and has a weight of W_i.

You can repeatedly perform the operation of choosing an item and moving it to another box zero or more times. If the weight of the item being moved is w, the cost of the operation is w.

Find the minimum total cost required to make each box contain exactly one item.

Constraints

• 1 \leq N \leq 10^{5}
• 1 \leq A_i \leq N (1 \leq i \leq N)
• 1 \leq W_i \leq 10^{4} (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
2 2 3 3 5
33 40 2 12 16

Sample Output 1

35

With the following two moves, you can make each box contain exactly one item:

• Move item 1 from box 2 to box 1. The cost is 33.
• Move item 3 from box 3 to box 4. The cost is 2.

The total cost of these two moves is 35. It is impossible to make each box contain exactly one item with a cost less than 35, so print 35.

Sample Input 2

12
3 6 7 4 12 4 8 11 11 1 8 11
3925 9785 9752 3587 4013 1117 3937 7045 6437 6208 3391 6309

Sample Output 2

17254

Problem Statement

We have a string S. Initially, S= 1.
Process Q queries in the following formats in order.

• 1 x : Append a digit x at the end of S.
• 2 : Delete the digit at the beginning of S.
• 3 : Print the number represented by S in decimal, modulo 998244353.

Constraints

• 1 \leq Q \leq 6 \times 10^5
• For each query in the first format, x \in \{1,2,3,4,5,6,7,8,9\}.
• A query in the second format is given only if S has a length of 2 or greater.
• There is at least one query in the third format.

Sample Input 1

3
3
1 2
3

Sample Output 1

1
12

In the first query, S is 1, so you should print 1 modulo 998244353, that is, 1.
In the second query, S becomes 12.
In the third query, S is 12, so you should print 12 modulo 998244353, that is, 12.

Sample Input 2

3
1 5
2
3

Sample Output 2

5

Sample Input 3

11
1 9
1 9
1 8
1 2
1 4
1 4
1 3
1 5
1 3
2
3

Sample Output 3

0

Be sure to print numbers modulo 998244353.