Problem Statement

Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.

Each square of X is painted as follows.

• Each tile is either a white tile or a black tile.
• Every square in a white tile is painted white; every square in a black tile is painted black.
• Tile (1,1) is a white tile.
• Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Print the grid X in the format specified in the Output section.

Constraints

• 1 \leq N,A,B \leq 10
• All values in input are integers.

Sample Input 1

4 3 2

Sample Output 1

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

Sample Input 2

5 1 5

Sample Output 2

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

Sample Input 3

4 4 1

Sample Output 3

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

Sample Input 4

1 4 4

Sample Output 4

....
....
....
....

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row (1\le i\le H) from the top and the j-th column (1\le j\le W) from the left.

Each cell is painted with one color, white or black. The color painted on the cells is represented by H strings S _ 1,S _ 2,\ldots,S _ H. When the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is ., cell (i,j) is painted white, and when the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is #, cell (i,j) is painted black.

Determine whether the grid satisfies the following condition:

• For every black cell, the number of horizontally or vertically adjacent cells that are painted black is 2 or 4.

Here, cells (i,j)\ (1\le i\le H,1\le j\le W) and (k,l)\ (1\le k\le H,1\le l\le W) are horizontally or vertically adjacent if and only if |i-k|+|j-l|=1.

Constraints

• 1\le H\le 20
• 1\le W\le 20
• H and W are integers.
• S _ i is a string of length W consisting of . and # (1\le i\le H).

Sample Input 1

8 7
.######
##....#
#.###.#
#.#.#.#
#.#.#.#
#.#####
#...#..
#####..

Sample Output 1

Yes

For example, cell (6,3) is painted black, and among the adjacent cells (5,3),(6,2),(6,4),(7,3), cells (5,3) and (6,4) are painted black, which is 2 cells, so it satisfies the condition.

Every other black cell also satisfies the condition, so output Yes.

Sample Input 2

1 2
##

Sample Output 2

No

Cell (1,1) is painted black, but it has only one adjacent cell, so it does not satisfy the condition.

Therefore, output No.

Sample Input 3

4 3
...
...
...
...

Sample Output 3

Yes

There are no black cells, so the condition is satisfied.

Therefore, output Yes.

Sample Input 4

15 18
##.###..##.##..##.
##.#.##.##.##.####
...##.#.......####
###.###....###.##.
#.##.......#.#....
#..#.##.##.#.#....
#.########.####.##
#.##.##.#....##.##
#......##.........
##.##..#..##..####
.#.#####..#####..#
.#..#...##.#.....#
.#..#.####.#.....#
.##.#.#.#..##..###
..###.###...####..

Sample Output 4

Yes

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the square at the i-th row from the top and the j-th column from the left.
Initially, there was one cookie on each square inside a rectangle whose height and width were at least 2 squares long, and no cookie on the other squares.
Formally, there was exactly one quadruple of integers (a,b,c,d) that satisfied all of the following conditions.

• 1 \leq a \lt b \leq H
• 1 \leq c \lt d \leq W
• There was one cookie on each square (i, j) such that a \leq i \leq b, c \leq j \leq d, and no cookie on the other squares.

However, Snuke took and ate one of the cookies on the grid.
The square that contained that cookie is now empty.

As the input, you are given the state of the grid after Snuke ate the cookie.
The state of the square (i, j) is given as the character S_{i,j}, where # means a square with a cookie, and . means a square without one.
Find the square that contained the cookie eaten by Snuke. (The answer is uniquely determined.)

Constraints

• 2 \leq H, W \leq 500
• S_{i,j} is # or ..

Sample Input 1

5 6
......
..#.#.
..###.
..###.
......

Sample Output 1

2 4

Initially, cookies were on the squares inside the rectangle with (2, 3) as the top-left corner and (4, 5) as the bottom-right corner, and Snuke ate the cookie on (2, 4). Thus, you should print (2, 4).

Sample Input 2

3 2
#.
##
##

Sample Output 2

1 2

Initially, cookies were placed on the squares inside the rectangle with (1, 1) as the top-left corner and (3, 2) as the bottom-right corner, and Snuke ate the cookie at (1, 2).

Sample Input 3

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

Sample Output 3

2 5

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

• All input values are integers.
• 1 \le K
• At least K 321-like Numbers exist.

Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.

Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210

Problem Statement

Takahashi is about to go buy eel at a fish shop.

The town where he lives is divided into a grid of H rows and W columns. Each cell is either a road or a wall.
Let us denote the cell at the i-th row from the top (1\leq i \leq H) and the j-th column from the left (1\leq j \leq W) as cell (i,j).
Information about each cell is given by H strings S_1,S_2,\ldots,S_H, each of length W. Specifically, if the j-th character of S_i (1\leq i \leq H,1\leq j\leq W) is ., cell (i,j) is a road; if it is #, cell (i,j) is a wall.

He can repeatedly perform the following two types of actions in any order:

• Move to an adjacent cell (up, down, left, or right) that is within the town and is a road.
• Choose one of the four directions (up, down, left, or right) and perform a front kick in that direction.
  When he performs a front kick, for each of the cells at most 2 steps away in that direction from the cell he is currently in, if that cell is a wall, it becomes a road.
  If some of the cells at most 2 steps away are outside the town, a front kick can still be performed, but anything outside the town does not change.

He starts in cell (A,B), and he wants to move to the fish shop in cell (C,D).
It is guaranteed that both the cell where he starts and the cell with the fish shop are roads.
Find the minimum number of front kicks he needs in order to reach the fish shop.

Constraints

• 1\leq H\leq 1000
• 1\leq W\leq 1000
• Each S_i is a string of length W consisting of . and #.
• 1\leq A,C\leq H
• 1\leq B,D\leq W
• (A,B)\neq (C,D)
• H, W, A, B, C, and D are integers.
• The cell where Takahashi starts and the cell with the fish shop are roads.

Sample Input 1

10 10
..........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
.##.#.#.#.
###.#.#.#.
###.#.#.#.
#.....#...
1 1 7 1

Sample Output 1

1

Takahashi starts in cell (1,1).
By repeatedly moving to adjacent road cells, he can reach cell (7,4).
If he performs a front kick to the left from cell (7,4), cells (7,3) and (7,2) turn from walls to roads.
Then, by continuing to move through road cells (including those that have become roads), he can reach the fish shop in cell (7,1).

In this case, the number of front kicks performed is 1, and it is impossible to reach the fish shop without performing any front kicks, so print 1.

Sample Input 2

2 2
.#
#.
1 1 2 2

Sample Output 2

1

Takahashi starts in cell (1,1).
When he performs a front kick to the right, cell (1,2) turns from a wall to a road.
The cell two steps to the right of (1,1) is outside the town, so it does not change.
Then, he can move to cell (1,2) and then to the fish shop in cell (2,2).

In this case, the number of front kicks performed is 1, and it is impossible to reach the fish shop without performing any front kicks, so print 1.

Sample Input 3

1 3
.#.
1 1 1 3

Sample Output 3

1

When performing a front kick, it is fine if the fish shop’s cell is within the cells that could be turned into a road. Specifically, the fish shop’s cell is a road from the beginning, so it remains unchanged; particularly, the shop is not destroyed by the front kick.

Sample Input 4

20 20
####################
##...##....###...###
#.....#.....#.....##
#..#..#..#..#..#..##
#..#..#....##..#####
#.....#.....#..#####
#.....#..#..#..#..##
#..#..#.....#.....##
#..#..#....###...###
####################
####################
##..#..##...###...##
##..#..#.....#.....#
##..#..#..#..#..#..#
##..#..#..#..#..#..#
##.....#..#..#..#..#
###....#..#..#..#..#
#####..#.....#.....#
#####..##...###...##
####################
3 3 18 18

Sample Output 4

3