Problem Statement

You are given a grid with N rows and N columns, where N is an even number. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Each cell is painted black or white. If A_{i, j} = #, cell (i, j) is black; if A_{i, j} = ., it is white.

Find the color of each cell after performing the following operation for i = 1, 2, \ldots, \frac{N}{2} in this order.

• For all pairs of integers x, y between i and N + 1 - i, inclusive, replace the color of cell (y, N + 1 - x) with the color of cell (x, y). Perform these replacements simultaneously for all such pairs x, y.

Constraints

• N is an even number between 2 and 3000, inclusive.
• Each A_{i, j} is # or ..

Sample Input 1

8
.......#
.......#
.####..#
.####..#
.##....#
.##....#
.#######
.#######

Sample Output 1

........
#######.
#.....#.
#.###.#.
#.#...#.
#.#####.
#.......
########

The operations change the colors of the grid cells as follows:

.......#   ........   ........   ........   ........
.......#   ######..   #######.   #######.   #######.
.####..#   ######..   #....##.   #.....#.   #.....#.
.####..# → ##..##.. → #....##. → #.##..#. → #.###.#.
.##....#   ##..##..   #..####.   #.##..#.   #.#...#.
.##....#   ##......   #..####.   #.#####.   #.#####.
.#######   ##......   #.......   #.......   #.......
.#######   ########   ########   ########   ########

Sample Input 2

6
.#.#.#
##.#..
...###
###...
..#.##
#.#.#.

Sample Output 2

#.#.#.
.#.#.#
#.#.#.
.#.#.#
#.#.#.
.#.#.#

Sample Input 3

12
.......#.###
#...#...#..#
###.#..#####
..#.#.#.#...
.#.....#.###
.......#.#..
#...#..#....
#####.......
...#...#.#.#
..###..#..##
#..#.#.#.#.#
.####.......

Sample Output 3

.#..##...##.
#.#.#.#.#...
###.##..#...
#.#.#.#.#...
#.#.##...##.
............
............
.###.###.###
...#...#.#..
.###...#.###
...#...#...#
.###...#.###

Problem Statement

We have a grid with H horizontal rows and W vertical columns. (i, j) denotes the square at the i-th row from the top and j-th column from the left.
(i,j) has a character G_{i,j} written on it. G_{i,j} is U, D, L, or R.

You are initially at (1,1). You repeat the following operation until you cannot make a move.

Let (i,j) be the square you are currently at.
If G_{i,j} is U and i \neq 1, move to (i-1,j).
If G_{i,j} is D and i \neq H, move to (i+1,j).
If G_{i,j} is L and j \neq 1, move to (i,j-1).
If G_{i,j} is R and j \neq W, move to (i,j+1).
Otherwise, you cannot make a move.

Print the square you end up at when you cannot make a move.
If you indefinitely repeat moving, print -1 instead.

Constraints

• 1 \leq H, W \leq 500
• G_{i,j} is U, D, L, or R.
• H and W are integers.

Sample Input 1

2 3
RDU
LRU

Sample Output 1

1 3

You will move as (1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (1, 3), ending up here, so the answer is (1, 3).

Sample Input 2

2 3
RRD
ULL

Sample Output 2

-1

You will indefinitely repeat moving as (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (1, 1) \to (1, 2) \to \dots, so -1 should be printed in this case.

Sample Input 3

9 44
RRDDDDRRRDDDRRRRRRDDDRDDDDRDDRDDDDDDRRDRRRRR
RRRDLRDRDLLLLRDRRLLLDDRDLLLRDDDLLLDRRLLLLLDD
DRDLRLDRDLRDRLDRLRDDLDDLRDRLDRLDDRLRRLRRRDRR
DDLRRDLDDLDDRLDDLDRDDRDDDDRLRRLRDDRRRLDRDRDD
RDLRRDLRDLLLLRRDLRDRRDRRRDLRDDLLLLDDDLLLLRDR
RDLLLLLRDLRDRLDDLDDRDRRDRLDRRRLDDDLDDDRDDLDR
RDLRRDLDDLRDRLRDLDDDLDDRLDRDRDLDRDLDDLRRDLRR
RDLDRRLDRLLLLDRDRLLLRDDLLLLLRDRLLLRRRRLLLDDR
RRRRDRDDRRRDDRDDDRRRDRDRDRDRRRRRRDDDRDDDDRRR

Sample Output 3

9 5

Problem Statement

You initially have an empty string S.
Additionally, there are bags 1, 2, \dots, N, each containing some strings.
Bag i contains A_i strings S_{i,1}, S_{i,2}, \dots, S_{i,A_i}.

You will repeat the following steps for i = 1, 2, \dots, N:

• Choose and perform one of the following two actions:
  • Pay 1 yen, select exactly one string from bag i, and concatenate it to the end of S.
  • Do nothing.

Given a string T, find the minimum amount of money required to make the final S equal T.
If there is no way to make the final S equal T, print -1.

Constraints

• T is a string consisting of lowercase English letters with length between 1 and 100, inclusive.
• N is an integer between 1 and 100, inclusive.
• A_i is an integer between 1 and 10, inclusive.
• S_{i,j} is a string consisting of lowercase English letters with length between 1 and 10, inclusive.

Sample Input 1

abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de

Sample Output 1

2

For example, doing the following makes the final S equal T with two yen, which can be shown to be the minimum amount required.

• For i=1, select abc from bag 1 and concatenate it to the end of S, making S= abc.
• For i=2, do nothing.
• For i=3, select de from bag 3 and concatenate it to the end of S, making S= abcde.

Sample Input 2

abcde
3
2 ab abc
3 f c bcde
1 e

Sample Output 2

-1

There is no way to make the final S equal T, so print -1.

Sample Input 3

aaabbbbcccc
6
2 aa aaa
2 dd ddd
2 ab aabb
4 bbaa bbbc bbb bbcc
2 cc bcc
3 ccc cccc ccccc

Sample Output 3

4

Problem Statement

You are given a directed graph with N vertices and M edges. The i-th edge (1 \leq i \leq M) is a directed edge from vertex u _ i to vertex v _ i.

Initially, you are at vertex 1. You want to repeat the following operations until you reach vertex N:

• Perform one of the two operations below:
  • Move along a directed edge from your current vertex. This incurs a cost of 1. More precisely, if you are at vertex v, choose a vertex u such that there is a directed edge from v to u, and move to vertex u.
  • Reverse the direction of all edges. This incurs a cost of X. More precisely, if and only if there was a directed edge from v to u immediately before this operation, there is a directed edge from u to v immediately after this operation.

It is guaranteed that, for the given graph, you can reach vertex N from vertex 1 by repeating these operations.

Find the minimum total cost required to reach vertex N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq X \leq 10^9
• 1 \leq u _ i \leq N \ (1 \leq i \leq M)
• 1 \leq v _ i \leq N \ (1 \leq i \leq M)
• For the given graph, it is guaranteed that you can reach vertex N from vertex 1 by the operations described.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

The given graph looks like this:

You can reach vertex 5 with a total cost of 4 by doing the following:

• Move to vertex 2 at a cost of 1.
• Move to vertex 4 at a cost of 1.
• Move to vertex 3 at a cost of 1.
• Move to vertex 5 at a cost of 1.

It is impossible to reach vertex 5 with a total cost of 3 or less, so print 4.

Sample Input 2

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

Sample Output 2

3

The graph is the same as in Sample 1, but the cost to reverse edges is different.

You can reach vertex 5 with a total cost of 3 as follows:

• Move to vertex 2 at a cost of 1.
• Reverse all edges at a cost of 1.
• Move to vertex 5 at a cost of 1.

It is impossible to reach vertex 5 with a total cost of 2 or less, so print 3.

Sample Input 3

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

Sample Output 3

4294967299

Note that the answer may exceed the 32-bit integer range.

Sample Input 4

20 13 5
1 3
14 18
18 17
12 19
3 5
4 6
13 9
8 5
14 2
20 18
8 14
4 9
14 8

Sample Output 4

21

Problem Statement

There are N scaffolds numbered from 1 to N arranged in a line. The height of scaffold i(1 \leq i \leq N) is H_i.

Takahashi decides to play a game of moving on the scaffolds. Initially, he freely chooses an integer i(1 \leq i \leq N) and gets on scaffold i.

When he is on scaffold i at some point, he can choose an integer j(1 \leq j \leq N) satisfying the following condition and move to scaffold j:

• H_j \leq H_i - D and 1 \leq |i-j| \leq R.

Find the maximum number of moves he can make when he repeats moving until he can no longer move.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq D,R \leq N
• H is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

5 2 1
5 3 1 4 2

Sample Output 1

2

Takahashi initially gets on scaffold 1 and can move between the scaffolds as follows:

• First move: Since H_2 \leq H_1 -D and |2-1| \leq R, he can move to scaffold 2. Move from scaffold 1 to scaffold 2.
• Second move: Since H_3 \leq H_2 -D and |3-2| \leq R, he can move to scaffold 3. Move from scaffold 2 to scaffold 3.
• Since the height of scaffold 3 is 1, he can no longer move.

As shown above, he can move 2 times. Also, no matter how he chooses the scaffolds to move to, he cannot move 3 or more times. Therefore, output 2.

Sample Input 2

13 3 2
13 7 10 1 9 5 4 11 12 2 8 6 3

Sample Output 2

3