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.

Input

The input is given from Standard Input in the following format:

~S~

Output

Print the answer.

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.

Input

The input is given from Standard Input in the following format:

~N~ ~M~ ~A_1~ ~B_1~ ~\vdots~ ~A_M~ ~B_M~

Output

Print ~N~ lines as specified in the Problem Statement.

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.

What are permutations?

A permutation of ~(1, \dots, N)~ is an arrangement of ~(1, \dots, N)~ into a sequence.

What is lexicographical order?

For sequences of length ~N~ , ~A = (A_1, \dots, A_N)~ and ~B = (B_1, \dots, B_N)~ , ~A~ is said to be strictly lexicographically smaller than ~B~ if and only if there is an integer ~1 \leq i \leq N~ that satisfies both of the following.

• ~(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1}).~
• ~A_i < B_i~ .

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.

Input

The input is given from Standard Input in the following format:

~N~

~P_1~ ~\ldots~ ~P_N~

Output

Let ~Q = (Q_1, \dots, Q_N)~ be the sought permutation. Print ~Q_1, \dots, Q_N~ in a single line in this order, separated by spaces.

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.

Input

The input is given from Standard Input in the following format:

~N~

~a_1~ ~a_2~ ~\ldots~ ~a_N~

Output

Print the answer.

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 .

Input

The input is given from Standard Input in the following format:

~H~ ~W~ ~C_{1, 1} \ldots C_{1, W}~ ~\vdots~ ~C_{H, 1} \ldots C_{H, W}~

Output

If there is a path that satisfies the conditions in the Problem Statement, print Yes ; otherwise, print No .

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