Problem Statement

There is a grid with H rows and W columns.

Each cell of the grid is land or sea, which is represented by H strings S_1, S_2, \ldots, S_H of length W. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left, and (i, j) is land if the j-th character of S_i is ., and (i, j) is sea if the character is #.

The constraints guarantee that all cells on the perimeter of the grid (that is, the cells (i, j) that satisfy at least one of i = 1, i = H, j = 1, j = W) are sea.

Takahashi's spaceship has crash-landed on a cell in the grid. Afterward, he moved N times on the grid following the instructions represented by a string T of length N consisting of L, R, U, and D. For i = 1, 2, \ldots, N, the i-th character of T describes the i-th move as follows:

• L indicates a move of one cell to the left. That is, if he is at (i, j) before the move, he will be at (i, j-1) after the move.
• R indicates a move of one cell to the right. That is, if he is at (i, j) before the move, he will be at (i, j+1) after the move.
• U indicates a move of one cell up. That is, if he is at (i, j) before the move, he will be at (i-1, j) after the move.
• D indicates a move of one cell down. That is, if he is at (i, j) before the move, he will be at (i+1, j) after the move.

It is known that all cells along his path (including the cell where he crash-landed and the cell he is currently on) are not sea. Print the number of cells that could be his current position.

Constraints

• H, W, and N are integers.
• 3 \leq H, W \leq 500
• 1 \leq N \leq 500
• T is a string of length N consisting of L, R, U, and D.
• S_i is a string of length W consisting of . and #.
• There is at least one cell that could be Takahashi's current position.
• All cells on the perimeter of the grid are sea.

Sample Input 1

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

Sample Output 1

2

The following two cases are possible, so there are two cells that could be Takahashi's current position: (3, 4) and (4, 5).

• He crash-landed on cell (3, 5) and moved (3, 5) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4).
• He crash-landed on cell (4, 6) and moved (4, 6) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (3, 4) \rightarrow (4, 4) \rightarrow (4, 5).

Sample Input 2

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

Sample Output 2

6

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq A_i \leq 10^{9}
• 1 \leq C_i \leq 10^{9}
• All input values are integers.

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

• There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
• There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35

Problem Statement

You are given an integer sequence of length N: A=(A_1,A_2,\ldots,A_N).

You will perform the following consecutive operations just once:

• Choose an integer x (0\leq x \leq N). If x is 0, do nothing. If x is 1 or greater, replace each of A_1,A_2,\ldots,A_x with L.

• Choose an integer y (0\leq y \leq N). If y is 0, do nothing. If y is 1 or greater, replace each of A_{N},A_{N-1},\ldots,A_{N-y+1} with R.

Print the minimum possible sum of the elements of A after the operations.

Constraints

• 1 \leq N \leq 2\times 10^5
• -10^9 \leq L, R\leq 10^9
• -10^9 \leq A_i\leq 10^9
• All values in input are integers.

Sample Input 1

5 4 3
5 5 0 6 3

Sample Output 1

14

If you choose x=2 and y=2, you will get A = (4,4,0,3,3), for the sum of 14, which is the minimum sum achievable.

Sample Input 2

4 10 10
1 2 3 4

Sample Output 2

10

If you choose x=0 and y=0, you will get A = (1,2,3,4), for the sum of 10, which is the minimum sum achievable.

Sample Input 3

10 -5 -3
9 -6 10 -1 2 10 -1 7 -15 5

Sample Output 3

-58

L, R, and A_i may be negative.

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered from 1 through N, and the edges are numbered from 1 through M. Edge i connects Vertex U_i and Vertex V_i.

You are given integers K, S, T, and X. How many sequences A = (A_0, A_1, \dots, A_K) are there satisfying the following conditions?

• A_i is an integer between 1 and N (inclusive).
• A_0 = S
• A_K = T
• There is an edge that directly connects Vertex A_i and Vertex A_{i+1}.
• Integer X\ (X≠S,X≠T) appears even number of times (possibly zero) in sequence A.

Since the answer can be very large, find the answer modulo 998244353.

Constraints

• All values in input are integers.
• 2≤N≤2000
• 1≤M≤2000
• 1≤K≤2000
• 1≤S,T,X≤N
• X≠S
• X≠T
• 1≤U_i<V_i≤N
• If i ≠ j, then (U_i, V_i) ≠ (U_j, V_j).

Sample Input 1

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

Sample Output 1

4

The following 4 sequences satisfy the conditions:

• (1, 2, 1, 2, 3)
• (1, 2, 3, 2, 3)
• (1, 4, 1, 4, 3)
• (1, 4, 3, 4, 3)

On the other hand, (1, 2, 3, 4, 3) and (1, 4, 1, 2, 3) do not, since there are odd number of occurrences of 2.

Sample Input 2

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

Sample Output 2

0

The graph is not necessarily connected.

Sample Input 3

10 15 20 4 4 6
2 6
2 7
5 7
4 5
2 4
3 7
1 7
1 4
2 9
5 10
1 3
7 8
7 9
1 6
1 2

Sample Output 3

952504739

Find the answer modulo 998244353.

Problem Statement

We have a grid with N rows and M columns. The square (i,j) at the i-th row from the top and j-th column from the left has an integer (i-1) \times M + j written on it.
Let us perform the following operation on this grid.

• For every square (i,j) such that i+j is odd, replace the integer on that square with 0.

Answer Q questions on the grid after the operation.
The i-th question is as follows:

• Find the sum of the integers written on all squares (p,q) that satisfy all of the following conditions, modulo 998244353.
  • A_i \le p \le B_i.
  • C_i \le q \le D_i.

Constraints

• All values in the input are integers.
• 1 \le N,M \le 10^9
• 1 \le Q \le 2 \times 10^5
• 1 \le A_i \le B_i \le N
• 1 \le C_i \le D_i \le M

Sample Input 1

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

Sample Output 1

28
27
36
14
0
104

The grid in this input is shown below.

This input contains six questions.

• The answer to the first question is 0+3+0+6+0+8+0+11+0=28.
• The answer to the second question is 1+0+9+0+17=27.
• The answer to the third question is 17+0+19+0=36.
• The answer to the fourth question is 14.
• The answer to the fifth question is 0.
• The answer to the sixth question is 104.

Sample Input 2

1000000000 1000000000
3
1000000000 1000000000 1000000000 1000000000
165997482 306594988 719483261 992306147
1 1000000000 1 1000000000

Sample Output 2

716070898
240994972
536839100

For the first question, note that although the integer written on the square (10^9,10^9) is 10^{18}, you are to find it modulo 998244353.

Sample Input 3

999999999 999999999
3
999999999 999999999 999999999 999999999
216499784 840031647 84657913 415448790
1 999999999 1 999999999

Sample Output 3

712559605
648737448
540261130