Problem Statement

You are given an integer N and a string S consisting of lowercase English letters with length less than N.

Print the string obtained by repeatedly adding the lowercase English letter o to the beginning of S until its length becomes N.

Constraints

• 2\leq N \leq 100
• N is an integer.
• S is a string consisting of lowercase English letters with length between 1 and N - 1, inclusive.

Sample Input 1

5
abc

Sample Output 1

ooabc

Since N=5 and the length of S is 3, the answer is the string obtained by adding 5-3=2 os to the beginning of S.

Sample Input 2

2
o

Sample Output 2

oo

Sample Input 3

12
vgxgpuam

Sample Output 3

oooovgxgpuam

Problem Statement

You are given an odd number N that is at least 3.

There is a grid with N rows and N columns, where all cells are initially empty. Now, you will write integers in each cell of this grid according to the following procedure. Let (i,j) denote the cell at the (i+1)-th row from the top and (j+1)-th column from the left (0\leq i<N, 0\leq j<N).

1. Write 1 in cell (0,\frac{N-1}{2}).
2. Repeat the following operation N^2-1 times:
   • Let (r,c) be the cell where an integer was written last time, and k be the integer written. If cell ((r-1) \bmod N, (c+1) \bmod N) is empty, write k+1 in that cell; otherwise, write k+1 in cell ((r+1) \bmod N,c). Here, x \bmod N denotes the remainder when x is divided by N.

Find the integer that will be written in each cell in this procedure. It can be proved that each cell will have an integer written in it exactly once.

Constraints

• 3\leq N \leq 99
• N is an odd number.

Sample Input 1

3

Sample Output 1

8 1 6
3 5 7
4 9 2

Integers are written in each cell as follows:

1. Write 1 in cell (0,\frac{3-1}{2})=(0,1).
2. Cell ((0-1) \bmod 3, (1+1) \bmod 3)=(2,2) is empty, so write 2 there.
3. Cell ((2-1) \bmod 3, (2+1) \bmod 3)=(1,0) is empty, so write 3 there.
4. Cell ((1-1) \bmod 3, (0+1) \bmod 3)=(0,1) is not empty, so write 4 in cell ((1+1) \bmod 3,0)=(2,0).
5. \vdots

Sample Input 2

5

Sample Output 2

17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3
11 18 25 2 9

Problem Statement

There is a grid with N rows and N columns. Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. Initially, nothing is placed on the grid.

You will now perform M operations. The i-th operation (1\leq i\leq M) is as follows:

• Place a block that occupies a 2 \times 2 region with cell (R_i,C_i) as the top-left corner on the grid if and only if its position does not overlap with any other blocks already placed. More precisely, for the set of cells S=\lbrace (R_i,C_i),(R_i+1,C_i),(R_i,C_i+1),(R_i+1,C_i+1)\rbrace, if there exists a block already placed on the grid that occupies any cell in S, do nothing; otherwise, place a block that occupies all four cells in S.

After performing all operations, find how many blocks are placed on the grid.

Constraints

• 2\leq N \leq 10^9
• 1\leq M \leq 2\times 10^5
• 1\leq R_i,C_i \leq N-1
• All input values are integers.

Sample Input 1

4 3
1 1
2 2
2 3

Sample Output 1

2

The following diagram shows the operations, where black-filled regions represent blocks and red-framed regions represent where the next block is to be placed.

• Operation 1: Nothing is placed in the 2 \times 2 region with cell (1,1) as the top-left corner, so place a block there.
• Operation 2: Among the 2 \times 2 region with cell (2,2) as the top-left corner, there is already another block on cell (2,2), so do nothing.
• Operation 3: Nothing is placed in the 2 \times 2 region with cell (2,3) as the top-left corner, so place a block there.

Thus, after performing all operations, two blocks are placed on the grid.

Sample Input 2

1000000000 4
1 1
1 101
101 1
101 101

Sample Output 2

4

Blocks can be placed in all operations.

Sample Input 3

8 10
6 5
7 3
6 7
3 4
4 2
3 7
1 3
7 4
6 1
6 1

Sample Output 3

8

There may exist i,j\ (i\neq j) such that (R_i,C_i)=(R_j,C_j).

Problem Statement

There is a maze consisting of 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. The type of cell (i,j) is given as a character S_{i,j}, where each character has the following meaning:

• . : Empty cell
• # : Obstacle cell
• Lowercase English letter (a - z): Warp cell

In the maze, you can perform the following two types of actions any number of times in any order:

• Walk: Move from the current cell to a cell that is one cell away in one of the four directions (up, down, left, right). However, you cannot move to an obstacle cell or outside the grid.
• Warp: When you are at a warp cell, move to any warp cell with the same character written on it.

Determine whether it is possible to move from cell (1,1) to cell (H,W), and if possible, find the minimum total number of actions required.

Constraints

• 1\leq H,W \leq 1000
• H\times W \geq 2
• H and W are integers.
• S_{i,j} is ., #, or a lowercase English letter.
• S_{1,1}\neq #
• S_{H,W}\neq #

Sample Input 1

3 4
..a.
####
ba#b

Sample Output 1

5

You can move from cell (1,1) to cell (3,4) by performing actions as follows:

1. Move from cell (1,1) to cell (1,2) by walking.
2. Move from cell (1,2) to cell (1,3) by walking.
3. Move from cell (1,3) to cell (3,2) by warping.
4. Move from cell (3,2) to cell (3,1) by walking.
5. Move from cell (3,1) to cell (3,4) by warping.

The total number of actions is 5, which is the minimum.

Sample Input 2

3 4
..a.
####
b.#b

Sample Output 2

-1

It is impossible to move from cell (1,1) to cell (3,4).

Sample Input 3

4 4
xxxx
xxxx
xxxx
xxxx

Sample Output 3

1

Sample Input 4

7 11
u..#y..#...
k..#.z.#.k.
iju#...#x..
###########
..x#.t.#..n
abc#y..#...
..z#..t#.y.

Sample Output 4

12

Problem Statement

You are given an integer sequence P=(P _ 1,P _ 2,\ldots,P _ N) that is a permutation of (1,2,\ldots,N). Here, it is guaranteed that P is not equal to (1,2,\ldots,N).

You want to perform the following operation zero or more times to make P match the sequence (1,2,\ldots,N):

• Choose a pair of integers (i,j) satisfying 1\le i\lt j\le N. Swap the values of P _ i and P _ j.

Let K be the minimum number of operations required to make P match the sequence (1,2,\ldots,N).

Find the number of operations that can be the first operation in a sequence of operations that makes P match the sequence (1,2,\ldots,N) in K operations. Two operations are distinguished if and only if the chosen pairs of integers (i,j) are different.

Constraints

• 2\le N\le3\times10 ^ 5
• 1\le P _ i\le N\ (1\le i\le N)
• P _ i\ne P _ j\ (1\le i\lt j\le N)
• There exists 1\le i\le N such that i\ne P _ i.
• All input values are integers.

Sample Input 1

5
3 1 4 2 5

Sample Output 1

6

For example, the goal can be achieved in three operations as follows:

• Choose (i,j)=(1,2). P becomes (1,3,4,2,5).
• Choose (i,j)=(2,4). P becomes (1,2,4,3,5).
• Choose (i,j)=(3,4). P becomes (1,2,3,4,5).

The goal cannot be achieved in two or fewer operations, so K=3.

As explained above, choosing (1,2) for the first operation allows the goal to be achieved in three operations. Additionally, if one of (1,3),(1,4),(2,3),(2,4),(3,4) is chosen for the first operation, then by performing the next two operations appropriately, P can be made equal to (1,2,3,4,5).

Therefore, print 6.

Sample Input 2

2
2 1

Sample Output 2

1

Sample Input 3

20
15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1

Sample Output 3

77

Problem Statement

In the night sky seen from planet AtCoder, there are N stars, and these N stars are arranged in a line from east to west. The i-th star from the east (1\le i\le N) is the B _ i-th brightest among these stars.

Takahashi decided to take a picture of the night sky using the following procedure:

1. Choose a pair of integers (l,r) satisfying 1\le l\le r\le N, and set up the camera so that the l-th, (l+1)-th, \ldots, r-th stars from the east all fit in the frame, and no other stars enter the frame.
2. Choose an integer b satisfying 1\le b\le N, and open the shutter so that all stars among the N stars whose brightness ranks from 1st through b-th (and that fit in the frame) are captured, and no other stars are captured.

However, he may not take a picture with no stars captured.

Find the number of different sets of stars that can be captured in pictures taken in this way.

Constraints

• 1\le N\le5\times10 ^ 5
• 1\le B _ i\le N\ (1\le i\le N)
• B _ i\ne B _ j\ (1\le i\lt j\le N)
• All input values are integers.

Sample Input 1

4
3 1 4 2

Sample Output 1

12

For example, with (l,r)=(2,4),b=3, you can take a picture with two stars: the 2nd star from the east and the 4th star from the east.

Including this, you can take pictures with the following 12 different sets of stars. In each picture, stars further east are arranged further left, and the i-th brightest star is labeled with integer i.

No other sets can be captured, so print 12.

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

28

Sample Input 3

20
15 5 13 17 9 11 20 4 14 16 6 3 8 19 12 7 10 18 2 1

Sample Output 3

627

Problem Statement

You are given a length-N sequence of positive integers A=(A _ 1,A _ 2,\ldots,A _ N) and a positive integer M.

Find the number of length-N sequences of non-negative integers x=(x _ 1,x _ 2,\ldots,x _ N) that satisfy the following condition:

• \displaystyle\sum _ {i=1} ^ NA _ ix _ i\le M

The number can be very large, so find it modulo 998244353.

Constraints

• 1\le N\le100
• 1\le A _ i\le100\ (1\le i\le N)
• 1\le M\le10 ^ {18}
• All input values are integers.

Sample Input 1

4 6
5 4 3 2

Sample Output 1

10

The sequences x that satisfy the condition are the following 10: (0,0,0,0),(0,0,0,1),(0,0,0,2),(0,0,0,3),(0,0,1,0),(0,0,1,1),(0,0,2,0),(0,1,0,0),(0,1,0,1),(1,0,0,0).

Thus, print 10.

Sample Input 2

6 89
4 7 5 10 7 6

Sample Output 2

38469

Sample Input 3

1 1000000007
1

Sample Output 3

1755655

There are 1000000008 sequences x that satisfy the condition.

Print this modulo 998244353, which is 1755655.

Sample Input 4

20 738894495848985641
40 58 13 24 65 11 63 29 98 75 40 77 15 50 83 85 35 46 38 37

Sample Output 4

31156940