Problem Statement

You are given a string S consisting of lowercase English letters.
If a appears in S, print the last index at which it appears; otherwise, print -1. (The index starts at 1.)

Constraints

• S is a string of length between 1 and 100 (inclusive) consisting of lowercase English letters.

Sample Input 1

abcdaxayz

Sample Output 1

7

a appears three times in S. The last occurrence is at index 7, so you should print 7.

Sample Input 2

bcbbbz

Sample Output 2

-1

a does not appear in S, so you should print -1.

Sample Input 3

aaaaa

Sample Output 3

5

Problem Statement

There are N cities numbered 1, \dots, N, and M roads connecting cities.
The i-th road (1 \leq i \leq M) connects city A_i and city B_i.

Print N lines as follows.

• Let d_i be the number of cities directly connected to city i \, (1 \leq i \leq N), and those cities be city a_{i, 1}, \dots, city a_{i, d_i}, in ascending order.
• The i-th line (1 \leq i \leq N) should contain d_i + 1 integers d_i, a_{i, 1}, \dots, a_{i, d_i} in this order, separated by spaces.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) if (i \neq j).
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

3 2 3 6
2 1 5
2 1 6
0
2 2 6
3 1 3 5

The cities directly connected to city 1 are city 2, city 3, and city 6. Thus, we have d_1 = 3, a_{1, 1} = 2, a_{1, 2} = 3, a_{1, 3} = 6, so you should print 3, 2, 3, 6 in the first line in this order, separated by spaces.

Note that a_{i, 1}, \dots, a_{i, d_i} must be in ascending order. For instance, it is unacceptable to print 3, 3, 2, 6 in the first line in this order.

Sample Input 2

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

Sample Output 2

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

Problem Statement

You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).

Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.

Constraints

• 2 \leq N \leq 100
• 1 \leq P_i \leq N \, (1 \leq i \leq N)
• P_i \neq P_j \, (i \neq j)
• (P_1, \dots, P_N) \neq (1, \dots, N)
• All values in the input are integers.

Sample Input 1

3
3 1 2

Sample Output 1

2 3 1

Here are the permutations of (1, 2, 3) in ascending lexicographical order.

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

Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).

Sample Input 2

10
9 8 6 5 10 3 1 2 4 7

Sample Output 2

9 8 6 5 10 2 7 4 3 1

Problem Statement

You are given a sequence of positive integers: A=(a_1,a_2,\ldots,a_N).
You can choose and perform one of the following operations any number of times, possibly zero.

• Choose an integer i such that 1 \leq i \leq N and a_i is a multiple of 2, and replace a_i with \frac{a_i}{2}.
• Choose an integer i such that 1 \leq i \leq N and a_i is a multiple of 3, and replace a_i with \frac{a_i}{3}.

Your objective is to make A satisfy a_1=a_2=\ldots=a_N.
Find the minimum total number of times you need to perform an operation to achieve the objective. If there is no way to achieve the objective, print -1 instead.

Constraints

• 2 \leq N \leq 1000
• 1 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

3
1 4 3

Sample Output 1

3

Here is a way to achieve the objective in three operations, which is the minimum needed.

• Choose an integer i=2 such that a_i is a multiple of 2, and replace a_2 with \frac{a_2}{2}. A becomes (1,2,3).
• Choose an integer i=2 such that a_i is a multiple of 2, and replace a_2 with \frac{a_2}{2}. A becomes (1,1,3).
• Choose an integer i=3 such that a_i is a multiple of 3, and replace a_3 with \frac{a_3}{3}. A becomes (1,1,1).

Sample Input 2

3
2 7 6

Sample Output 2

-1

There is no way to achieve the objective.

Sample Input 3

6
1 1 1 1 1 1

Sample Output 3

0

Problem Statement

We have a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the i-th row from the top (1 \leq i \leq H) and j-th column from the left (1 \leq j \leq W).

Each square is one of the following: the initial point, a road, and an obstacle.
A square (i, j) is represented by a character C_{i, j}. The square is the initial point if C_{i, j} = S, a road if C_{i, j} = ., and an obstacle if C_{i, j} = #. There is exactly one initial point.

Determine whether there is a path of length 4 or greater that starts at the initial point, repeats moving vertically or horizontally to an adjacent square, and returns to the initial point without going through an obstacle or visiting the same square multiple times except at the beginning and the end.
More formally, determine whether there are an integer n and a sequence of squares (x_0, y_0), (x_1, y_1), \dots, (x_n, y_n) that satisfy the following conditions.

• n \geq 4.
• C_{x_0, y_0} = C_{x_n, y_n} = S.
• If 1 \leq i \leq n - 1, then C_{x_i, y_i} = ..
• If 1 \leq i \lt j \leq n - 1, then (x_i, y_i) \neq (x_j, y_j).
• If 0 \leq i \leq n - 1, then square (x_i, y_i) and square (x_{i+1}, y_{i+1}) are vertically or horizontally adjacent to each other.

Constraints

• 4 \leq H \times W \leq 10^6
• H and W are integers greater than or equal to 2.
• C_{i, j} is S, ., or #.
• There is exactly one (i, j) such that C_{i, j} = S.

Sample Input 1

4 4
....
#.#.
.S..
.##.

Sample Output 1

Yes

The path (3, 2) \rightarrow (2, 2) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 4) \rightarrow (2, 4) \rightarrow (3, 4) \rightarrow (3, 3) \rightarrow (3, 2) satisfies the conditions.

Sample Input 2

2 2
S.
.#

Sample Output 2

No

Sample Input 3

5 7
.#...#.
..#.#..
...S...
..#.#..
.#...#.

Sample Output 3

No

Problem Statement

There are N cards called card 1, card 2, \ldots, card N. On card i (1\leq i\leq N), an integer A_i is written.

For K=1, 2, \ldots, N, solve the following problem.

We have a bag that contains K cards: card 1, card 2, \ldots, card K.
Let us perform the following operation twice, and let x and y be the numbers recorded, in the recorded order.

Draw a card from the bag uniformly at random, and record the number written on that card. Then, return the card to the bag.

Print the expected value of \max(x,y), modulo 998244353 (see Notes).
Here, \max(x,y) denotes the value of the greater of x and y (or x if they are equal).

Notes

It can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} with two coprime integers P and Q, it can be proved that there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Print this R.

Constraints

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

Sample Input 1

3
5 7 5

Sample Output 1

5
499122183
443664163

For instance, the answer for K=2 is found as follows.

The bag contains card 1 and card 2, with A_1=5 and A_2=7 written on them, respectively.

• If you draw card 1 in the first draw and card 1 again in the second draw, we have x=y=5, so \max(x,y)=5.
• If you draw card 1 in the first draw and card 2 in the second draw, we have x=5 and y=7, so \max(x,y)=7.
• If you draw card 2 in the first draw and card 1 in the second draw, we have x=7 and y=5, so \max(x,y)=7.
• If you draw card 2 in the first draw and card 2 again in the second draw, we have x=y=7, so \max(x,y)=7.

These events happen with the same probability, so the sought expected value is \frac{5+7+7+7}{4}=\frac{13}{2}. We have 499122183\times 2\equiv 13 \pmod{998244353}, so 499122183 should be printed.

Sample Input 2

7
22 75 26 45 72 81 47

Sample Output 2

22
249561150
110916092
873463862
279508479
360477194
529680742

Problem Statement

Find the number of sequences of integers with N terms, A=(a_1,a_2,\ldots,a_N), that satisfy the following conditions, modulo 998244353.

• 0 \leq a_1 \leq a_2 \leq \ldots \leq a_N \leq M.
• For each i=1,2,\ldots,N-1, the remainder when a_i is divided by 3 is different from the remainder when a_{i+1} is divided by 3.

Constraints

• 2 \leq N \leq 10^7
• 1 \leq M \leq 10^7
• All values in the input are integers.

Sample Input 1

3 4

Sample Output 1

8

Here are the eight sequences that satisfy the conditions.

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

Sample Input 2

276 10000000

Sample Output 2

909213205

Be sure to find the count modulo 998244353.

Problem Statement

Determine whether there is an N-by-N matrix X that satisfies the following conditions, and present one such matrix if it exists. (Let x_{i,j} denote the element of X at the i-th row from the top and j-th column from the left.)

• x_{i,j} \in \{ 0,1,2 \} for every i and j (1 \leq i,j \leq N).
• The following holds for each i=1,2,\ldots,Q.
  • Let P = \prod_{a_i \leq j \leq b_i} \prod_{c_i \leq k \leq d_i} x_{j,k}. Then, P is congruent to e_i modulo 3.

Constraints

• 1 \leq N,Q \leq 2000
• 1 \leq a_i \leq b_i \leq N
• 1 \leq c_i \leq d_i \leq N
• e_i \in \{0,1,2 \}
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

Yes
0 2
1 2

For example, for i=2, we have P = \prod_{a_2 \leq j \leq b_2} \prod_{c_2 \leq k \leq d_2} x_{j,k}= \prod_{1 \leq j \leq 2} \prod_{2 \leq k \leq 2} x_{j,k}=x_{1,2} \times x_{2,2}.
In this sample output, we have x_{1,2}=2 and x_{2,2}=2, so P=2 \times 2 = 4, which is congruent to e_2=1 modulo 3.
It can be similarly verified that the condition is also satisfied for i=1 and i=3.

Sample Input 2

4 4
1 4 1 4 0
1 4 1 4 1
1 4 1 4 2
1 4 1 4 0

Sample Output 2

No