Problem Statement

Takahashi eats three plates for breakfast: rice, miso soup, and salad.

His table is long and narrow, so he arranged the three plates in a row. The arrangement is given by a string S, where the i-th plate from the left is rice if S_i is R, miso soup if S_i is M, and salad if S_i is S.

Determine whether the plate of rice is to the left of the plate of miso soup.

Constraints

• |S| = 3
• S contains one R, one M, and one S.

Sample Input 1

RSM

Sample Output 1

Yes

The plate of rice is at the 1st position from the left, and the plate of miso soup is at the 3rd position from the left. Since the plate of rice is to the left, print Yes.

Sample Input 2

SMR

Sample Output 2

No

The plates are arranged as salad, miso soup, and rice from left to right.

Problem Statement

You are given a string S of length N consisting of o and x, and integers L and R.

Determine whether all characters from the L-th through the R-th character of S are o.

Constraints

• 1\leq N \leq 100
• 1\leq L \leq R \leq N
• S is a string of length N consisting of o and x.
• N, L, and R are all integers.

Sample Input 1

10 6 8
xoxxooooxo

Sample Output 1

Yes

All characters from the 6-th through the 8-th character of S are o, so the answer is Yes.

Sample Input 2

9 6 8
xoxxoxoox

Sample Output 2

No

The 6-th character is x, so the answer is No.

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

You are given an integer sequence A = (A_1, A_2, \dots, A_N) of length N and a positive integer M.

Your goal is to make the following condition false by performing this operation between 0 and N times (inclusive): remove the last element of A.

• Condition: A contains every integer from 1 through M.

Find the minimum number of operations required.

Under the constraints of this problem, it can be proved that it is always possible to make the condition false by performing the operation between 0 and N times.

Constraints

• 1 \le M \le N \le 100
• 1 \le A_i \le M
• All input values are integers.

Sample Input 1

5 3
3 2 3 1 2

Sample Output 1

2

Initially, A = (3,2,3,1,2). Since A contains every integer from 1 through 3, the condition holds.

If you perform the operation once, A = (3,2,3,1). The condition still holds.

If you perform the operation once more, A = (3,2,3). The integer 1 is missing, so the condition no longer holds.

Therefore, the minimum required number of operations is 2.

Sample Input 2

4 3
1 3 1 3

Sample Output 2

0

Since A initially lacks the integer 2, the condition is already false, so no operation is needed.

Sample Input 3

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

Sample Output 3

6

Problem Statement

You are given a string S. Find the number of strings that can result from performing the following operation exactly once.

• Let N be the length of S. Choose a pair of integers (i,j) such that 1\leq i<j\leq N and swap the i-th and j-th characters of S.

It can be proved that you can always perform it under the constraints of this problem.

Constraints

• S is a string of length between 2 and 10^6, inclusive, consisting of lowercase English letters.

Sample Input 1

abc

Sample Output 1

3

The length of S is 3, so 1\leq i<j\leq 3 is satisfied by three pairs of integers (i,j): (1,2), (1,3), and (2,3).

• Swapping the 1-st and 2-nd characters of S results in S being bac.
• Swapping the 1-st and 3-rd characters of S results in S being cba.
• Swapping the 2-nd and 3-rd characters of S results in S being acb.

Therefore, the operation on abc results in one of the three strings: bac, cba, and acb, so print 3.

Sample Input 2

aaaaa

Sample Output 2

1

Swapping any two characters results in S remaining aaaaa. Thus, only one string can result from the operation.

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
  • 1 \le X_i \le 9 for all integers 1 \le i \le N;
  • |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

• N is an integer.
• 2 \le N \le 10^6

Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

Problem Statement

There are N sleighs numbered 1,2,\ldots, N.

R_i reindeer are required to pull sleigh i.

Additionally, each reindeer can pull at most one sleigh. More precisely, \sum_{k=1}^{m} R_{i_k} reindeer are required to pull m sleighs i_1, i_2, \ldots, i_m.

Find the answer to Q queries of the following form:

• You are given an integer X. Determine the maximum number of sleighs that can be pulled when there are X reindeer.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq R_i \leq 10^9
• 1 \leq X \leq 2 \times 10^{14}
• All input values are integers.

Sample Input 1

4 3
5 3 11 8
16
7
1000

Sample Output 1

3
1
4

When there are 16 reindeer, sleighs 1,2,4 can be pulled.

It is impossible to pull four sleighs with 16 reindeer, so the answer to query 1 is 3.

Sample Input 2

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

Sample Output 2

1
1
2
2
2
3

Sample Input 3

2 2
1000000000 1000000000
200000000000000
1

Sample Output 3

2
0

Problem Statement

There is a directed graph with N vertices numbered 1 to N and N edges.
The out-degree of every vertex is 1, and the edge from vertex i points to vertex a_i.
Count the number of pairs of vertices (u, v) such that vertex v is reachable from vertex u.

Here, vertex v is reachable from vertex u if there exists a sequence of vertices w_0, w_1, \dots, w_K of length K+1 that satisfies the following conditions. In particular, if u = v, it is always reachable.

• w_0 = u.
• w_K = v.
• For every 0 \leq i \lt K, there is an edge from vertex w_i to vertex w_{i+1}.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq a_i \leq N
• All input values are integers.

Sample Input 1

4
2 1 1 4

Sample Output 1

8

The vertices reachable from vertex 1 are vertices 1, 2.
The vertices reachable from vertex 2 are vertices 1, 2.
The vertices reachable from vertex 3 are vertices 1, 2, 3.
The vertex reachable from vertex 4 is vertex 4.
Therefore, the number of pairs of vertices (u, v) such that vertex v is reachable from vertex u is 8.
Note that the edge from vertex 4 is a self-loop, that is, it points to vertex 4 itself.

Sample Input 2

5
2 4 3 1 2

Sample Output 2

14

Sample Input 3

10
6 10 4 1 5 9 8 6 5 1

Sample Output 3

41

Problem Statement

You are given a simple undirected graph consisting of N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge connects vertices u_i and v_i. Also, for i = 1, 2, \ldots, N, vertex i is assigned a positive integer W_i, and there are A_i pieces placed on it.

As long as there are pieces on the graph, repeat the following operation:

• First, choose and remove one piece from the graph, and let x be the vertex on which the piece was placed.
• Choose a (possibly empty) set S of vertices adjacent to x such that \sum_{y \in S} W_y \lt W_x, and place one piece on each vertex in S.

Print the maximum number of times the operation can be performed.

It can be proved that, regardless of how the operation is performed, there will be no pieces on the graph after a finite number of iterations.

Constraints

• All input values are integers.
• 2 \leq N \leq 5000
• 1 \leq M \leq \min \lbrace N(N-1)/2, 5000 \rbrace
• 1 \leq u_i, v_i \leq N
• u_i \neq v_i
• i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
• 1 \leq W_i \leq 5000
• 0 \leq A_i \leq 10^9

Sample Input 1

6 6
1 2
2 3
3 1
3 4
1 5
5 6
9 2 3 1 4 4
1 0 0 0 0 1

Sample Output 1

5

In the following explanation, let A = (A_1, A_2, \ldots, A_N) represent the numbers of pieces on the vertices. Initially, A = (1, 0, 0, 0, 0, 1).

Consider performing the operation as follows:

• Remove one piece from vertex 1 and place one piece each on vertices 2 and 3. Now, A = (0, 1, 1, 0, 0, 1).
• Remove one piece from vertex 2. Now, A = (0, 0, 1, 0, 0, 1).
• Remove one piece from vertex 6. Now, A = (0, 0, 1, 0, 0, 0).
• Remove one piece from vertex 3 and place one piece on vertex 2. Now, A = (0, 1, 0, 0, 0, 0).
• Remove one piece from vertex 2. Now, A = (0, 0, 0, 0, 0, 0).

In this procedure, the operation is performed five times, which is the maximum possible number of times.

Sample Input 2

2 1
1 2
1 2
0 0

Sample Output 2

0

In this sample input, there are no pieces on the graph from the beginning.

Sample Input 3

10 20
4 8
1 10
1 7
5 9
9 10
8 10
7 5
1 4
7 3
8 7
2 8
5 8
4 2
5 1
7 2
8 3
3 4
8 9
7 10
2 3
25 5 1 1 16 5 98 3 21 1
35 39 32 11 35 37 14 29 36 1

Sample Output 3

1380