Problem Statement

Mr.E869120 lives in Takahashi Kingdom.
He works as a programmer in AtCodeer Inc, which there is a meeting that we must attend. The meeting is held every day at time 0.
In Takahashi kingdom, there are N cities, and they are called city 1, city 2, city 3, ..., city N from west to east. In addition, there is a road which connects between city i and city i+1 (1 \leq i \leq N - 1), and takes A_i minutes to move.

Something happened on a day of May 2031... He woke up and looked a watch - it was actually time 0, which is the meeting time!
He is going to be late for the meeting. Since AtCodeer Inc. is very strict for being late, he is very likely to be fired!

But he is able to use a magic: TIMELEAP. When he use it, the time will be back by T minutes. He can use TIMELEAP when he is in any city. For example, if T = 3 and he use TIMELEAP at time 8, then the time will be back to 5.
He want to minimize the number of use of TIMELEAP. To not be late for the meeting, how many TIMELEAP should he use?

Constraints

• N is an integer between 2 and 100 (inclusive)
• T is an integer between 1 and 100 (inclusive)
• A_i is an integer between 1 and 100 (inclusive)

Subtasks

This problem is separated several two subtasks, and you will get score of the subtask if your program prints the correct answer for all testcases for the subtask prepared.
The score for a program is the sum of score of subtasks of correct answer.

1. (100 points)：N = 2, T = 1
2. (100 points)：No additional constraints.

Sample Input 1

2 1
3

Sample Output 1

3

For example, if he does following move, the number of TIMELEAP will be 3.

1. Initially, Mr.E869120 is in city 1 and the time is 0.
   

2. Use TIMELEAP 3 times when he is in city 1. Now the time is -3.
   

3. Move from city 1 to city 2. Since it takes 3 minutes, now the time is 0. Note: It is allowed to arrive at city N at time 0.
   

Sample Input 2

3 4
5 6

Sample Output 2

3

Note this testcase is not included in Subtask 1.

Problem Statement

AtCoder Market is a supermarket consist of 1 \ 000 \ 000 \ 000 squares, connected like a straight line from left to right. Let "square i" the i-th leftmost square. In other words, square i and square i+1 is connected for all integer i \ (1 \leq i \leq 999 \ 999 \ 999).

One day, N buyers came to AtCoder Market for shopping. i-th buyer wants to buy two goods: one in square A_i, and the other in square B_i.

The owner of AtCoder Market, square1001, is going to install one entrance and one exit.
Entrance and exit can be installed at any square, and entrance and exit can be placed at the same sqauare.

Then, the i-th buyer will do shopping in the following way:

• Start from the entrance, then visit squares A_i, B_i, and goal at the exit. They will move in the shortest route.

For all buyers, it takes exactly 1 seconds to move to adjacent square.

What is the minimum sum of durations of shoppings, when the owner chooses the place of entrance and exit optimally?

Constraints

• 1 \leq N \leq 30
• 1 \leq A_i < B_i \leq 1 \ 000 \ 000 \ 000

Output

Print the minimal sum of duration of shopping (in second), in one line.

Note

In this constraints, the answer may not be included in the range of 32-bit integer.
To use 64-bit integers, for example in C / C++, we can use long long type, instead of int.

Sample Input 1

3
5 7
2 6
8 10

Sample Output 1

18

Think about installing entrance in square 5, and exit in square 7. Each buyers will move as follows:

• Buyer No.1：Square 5 -> 6 -> 7
• Buyer No.2：Square 5 -> 4 -> 3 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
• Buyer No.3：Square 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 9 -> 8 -> 7

(Bold character means that the buyer took the goods)

The buyers 1, 2, 3 will use 2, 8, 8 seconds, respectively, so the total shopping time will be 18 seconds.
There's no method for total shopping time to be shorter than 18 seconds.

Sample Input 2

5
1 71
43 64
13 35
14 54
79 85

Sample Output 2

334

When square1001 installs entrance in square 14 and exit in square 64, the total shopping time will be 334 seconds, and it is minimum.

Sample Input 3

11
15004200 341668840
277786703 825590503
85505967 410375631
797368845 930277710
90107929 763195990
104844373 888031128
338351523 715240891
458782074 493862093
189601059 534714600
299073643 971113974
98291394 443377420

Sample Output 3

8494550716

When square1001 installs entrance in square 189 \ 601 \ 059 and exit in square 715 \ 240 \ 891, the total shopping time will be 8 \ 494 \ 550 \ 716 seconds, and it is minimum.

Problem Statement

We have an H \times W grid whose squares are painted black or white.
The square at the i-th row from the top and the j-th column from the left is denoted as cell (i, j).
Cell (i, j) is painted black if c_{i,j} = #, and cell (i, j) is painted white if c_{i,j} = ..

Following picture is an example of grid which is H = 5, W = 5.

Let's think about connecting 1 \ 000 \ 000 \ 000 same H \times W grids like follows:

After connecting, the grid size will be H \times \left(10^9 \times W\right). Mr.square1001 wants to move from cell (1, 1) to cell (H, 10^9 \times W). In each moves, he can move only to cell (i + 1, j) or cell (i, j + 1) from cell (i, j). In addition, he can only pass on a white cell.
Is it possible to move from the top-left corner cell to the bottom-right corner cell?

Constraints

• H, W is an integer between 1 and 100 (inclusive)
• c_{i, j} is # or .
• c_{1, 1} = .
• c_{H, W} = .

Subtasks

This problem is separated several two subtasks, and you will get score of the subtask if your program prints the correct answer for all testcases for the subtask prepared.
The score for a program is the sum of score of subtasks of correct answer.

1. (60 points) : H = 1
2. (130 points) : H = 2
3. (210 points) : No additional constraints.

Sample Input 1

1 3
...

Sample Output 1

Yay!

The state of grid and an example of movement is as follows.

Sample Input 2

1 3
.#.

Sample Output 2

:(

In this case, there is no way to move. Even he cannot move from cell (1, 1) to (1, 3).

Sample Input 3

3 3
.##
...
##.

Sample Output 3

Yay!

The state of grid and an example of movement is as follows.

Sample Input 4

7 7
..###..
...#...
#.....#
##.#.##
#.....#
...#...
..###..

Sample Output 4

:(

Problem Statement

There is a very long straight road, from west to east. The road can be expressed as number line, which west is negative direction and east is positive direction.

There are N snowballs in the road. The i-th snowballs is at coordinate X_i and the radius is R_i. We can assume that shape of all snowballs are spheres.

E869120 is trying to make the largest possible snowballs by combining some of them.

When he moves a snowball by distance d, the radius of it will be decreased by d. When the radius becomes zero, the snowball disappears.
Also, he can combine two snowballs at the same coordinates. When he combines snowballs of radius r_1 and r_2, the radius of the combined snowball will be \left(r_1^3 + r_2^3\right)^{1/3}.

Calculate the maximum possible radius E869120 can make, please!

Constraints

• 1 \leq N \leq 100 \ 000
• 1 \leq X_i \leq 1 \ 000 \ 000 \ 000
• 1 \leq R_i \leq 1 \ 000 \ 000 \ 000

Subtasks / Scoring

This problem is separated several two subtasks, and you will get score of the subtask if your program prints the correct answer for all testcases for the subtask prepared.
The score for a program is the sum of score of subtasks of correct answer.

1. (70 points)：N = 2
2. (140 points)：N \leq 15
3. (250 points)：N \leq 1 \ 000
4. (140 points)：No additional constraints.

Sample Input 1

2
4 5
7 9

Sample Output 1

9.03280211228081065

If E869120 does the following operation, he can obtain a snowball of radius 737^{1/3} = 9.03280....

• Move 1-st snowball to the east by distance 3. Then, the radius will be decreased by 3 and become 2.
• Combine 1-st and 2-nd snowballs. The radius after combining will be \left(9^3 + 2^3\right)^{1/3} = 9.03280....

And this is the largest possible snowball he can make.

Sample Input 2

5
3 4
1 4
1 2
9 10
5 3

Sample Output 2

9.99999999999999645

4-th snowball has radius of 10 initially, but he cannot obtain the snowball larger than that, in this case.
In addition, this problem admits error less than 10^{-4} (see "Output" section for details), so printing like 9.9992 or `10.000869120' will also be correct.

Sample Input 3

9
815886884 307027576
432574413 156832535
869389414 537542354
8271358 844638329
34762585 93905560
445922147 508315922
476305579 724641385
15004200 341668840
277786703 825590503

Sample Output 3

1000677079.68994784

Although the radius and coordinate is 10^9 or less, the answer may exceed 10^9.

Problem Statement

There is a rectangular board with H \times W cells. The cell of i-th row and j-th column is denoted by (i, j).

There are coins in some cells. If S_{i, j} = o, there is one coin in (i, j). Otherwise, if S_{i, j} = x, there is no coins in (i, j).

E869120 will place a robot in cell with coin, and he will set the initial direction, choosing from up / down / left / right. Then, the robot will repeat the following actions.

• Collect the coins in the cell of robot. Then, rotate 90 degrees left or right. After that, jump to any cell with coin that advances at least 1 cells in the direction robot faces.

E869120's objective is to collect all coins in the board. Determine if there's a way to fulfill the objective when E869120 can decide initial cell/direction of robot, and the direction of rotation and destination of jumps for each action.

Constraints

• 2 \leq H \leq 100
• 2 \leq W \leq 100
• S_{i, j} is either o or x.
• There is at least 1 coin on the board.

Subtasks / Scoring

This problem is separated several two subtasks, and you will get score of the subtask if your program prints the correct answer for all testcases for the subtask prepared.
The score for a program is the sum of score of subtasks of correct answer.

1. (100 points)：N \leq 8
2. (110 points)：N \leq 16
3. (150 points)：H = 2
4. (440 points)：No additional constraints.

When we let N the number of coins on the board.

Sample Input 1

5 5
xooxx
xoxxo
xxoox
ooxoo
xoxxx

Sample Output 1

Possible

He can fulfill the objective by moving like the following picture.

Sample Input 2

2 9
oxxxxoxxo
oxoxxoxxo

Sample Output 2

Possible

He can fulfill the objective by moving like the following picture.

Sample Input 3

9 25
xxxxxxxxxxxxxxxxxxxxxxxxx
xxoooxxxoooxxooooxxxoooxx
xoxxxoxoxxxoxoxxxoxoxxxox
xoxxxxxoxxxoxoxxxoxoxxxxx
xxoooxxxoooxxooooxxoxxxxx
xxxxxoxoxxxoxoxxxxxoxxxxx
xoxxxoxoxxxoxoxxxxxoxxxox
xxoooxxxoooxxoxxxxxxoooxx
xxxxxxxxxxxxxxxxxxxxxxxxx

Sample Output 3

Impossible

He cannot collect all coins no matter how he commanded the robot.

Sample Input 4

6 6
oxxxxo
xoooxx
xoooox
xoooox
xxooxx
oxxxxo

Sample Output 4

Impossible

He cannot collect all coins no matter how he commanded the robot, also in this case...

Problem Statment

In Japan, school starts from April. Since E869120 wanted to play with other classmates, he came up with the following card game.

• There are N cards, which is numbered 1, 2, 3, ..., N.
• There are D species of colors in cards, which is numbered 0, 1, 2, ..., D-1.
• Card i is colored with color S_i \ (0 \leq S_i < D), and the number i is written on it.

The card game will be played by D players, with using the cards. The rule is following:

1. First, make a pile with card 1, 2, 3, ..., k. Card i should be located at i-th from topmost.
2. Repeat next operation (3.), K times.
3. Choose the random integer i between 1 and k (inclusive) with equal probability, and swap the i-th topmost card and (i+1)-th topmost card currently.
4. Distribute the cards to players. More precisely, player 1, 2, 3,..., D, 1, 2, 3, ..., D, 1, 2, 3, ..., D, 1, 2,... will get the 1, 2, 3, 4, 5, 6,..., k-th topmost card, respectively.
5. The score of player i is the total number written on cards himself/herself have with color (i-1).

Please note that, for operation 3., "(k+1)-th topmost cards" means "1-st topmost cards$ instead.

This game consists of N \div D rounds. In the i-th round, the game will be played at k = i \times D.
For each round, calculate the expected value of score for each players.

Please note that the format of output is different, due to the size matter of output. See "Output" section for details.

Constraints

• D is between 3 and 10 (inclusive).
• N is between 3 and 3 \ 000 \ 000 (inclusive).
• K is between 1 and 1 \ 000 \ 000 \ 000 (inclusive).
• S_i \ (1 \leq i \leq N) is either of 0, 1, 2, ..., D-1.

Subtasks / Scoring

This problem is separated several two subtasks, and you will get score of the subtask if your program prints the correct answer for all testcases for the subtask prepared.
The score for a program is the sum of score of subtasks of correct answer.

1. (50 points)：N \leq 10, D \leq 4, K = 1
2. (70 points)：N \leq 10, D \leq 4, K \leq 5
3. (80 points)：N \leq 50, D \leq 4, K \leq 300
4. (100 points)：N \leq 3 \ 000, D \leq 4, K \leq 300
5. (210 points)：N \leq 3 \ 000, D \leq 4
6. (130 points)：N \leq 50 \ 000, D \leq 4
7. (40 points)：N \leq 150 \ 000, D \leq 6
8. (40 points)：N \leq 300 \ 000, D \leq 8
9. (40 points)：N \leq 500 \ 000, D \leq 10
10. (40 points)：N \leq 800 \ 000, D \leq 10
11. (200 points)：N \leq 3 \ 000 \ 000, D \leq 10

Sample Input 1

3 3 1
012

Sample Output 1

0.333333333333
0.666666666667
1.000000000000

Let the initial arrangement of cards (1, 2, 3). After K=1 time "operation 3" in problem statement, the arrangement of cards, (1, 3, 2), (2, 1, 3), (3, 2, 1) will be equally probable with probability 1/3.

For each possibility, the scores of players will be following:

• (1, 3, 2)：Players' score will be 1, 0, 0
• (2, 1, 3)：Players' score will be 0, 0, 3
• (3, 2, 1)：Players' score will be 0, 2, 0

Thus, the expected value of players' score will be 1/3, 2/3, 1.

Sample Input 2

8 4 1
01123310

Sample Output 2

2.250000000000
4.500000000000
1.500000000000
0.625000000000

In 1-st round, the following 4 scenarios are equally possible.

• (1, 2, 4, 3)：Players' score will be 1, 2, 4, 0
• (1, 3, 2, 4)：Players' score will be 1, 3, 0, 0
• (2, 1, 3, 4)：Players' score will be 0, 0, 0, 0
• (4, 2, 3, 1)：Players' score will be 0, 2, 0, 0

Hence, the expected score for each players in 1-st round, will be 1/2, 7/4, 1, 0.

In 2-nd round, the following 8 scenarios are equally possible.

• (1, 2, 3, 4, 5, 6, 8, 7)：Players' score will be 1, 2, 0, 0
• (1, 2, 3, 4, 5, 7, 6, 8)：Players' score will be 1, 9, 0, 0
• (1, 2, 3, 4, 6, 5, 7, 8)：Players' score will be 1, 2, 0, 0
• (1, 2, 3, 5, 4, 6, 7, 8)：Players' score will be 1, 2, 0, 5
• (1, 2, 4, 3, 5, 6, 7, 8)：Players' score will be 1, 2, 4, 0
• (1, 3, 2, 4, 5, 6, 7, 8)：Players' score will be 1, 3, 0, 0
• (2, 1, 3, 4, 5, 6, 7, 8)：Players' score will be 0, 0, 0, 0
• (8, 2, 3, 4, 5, 6, 7, 1)：Players' score will be 8, 2, 0, 0

Hence, the expected score for each players in 2-nd round, will be 7/4, 11/4, 1/2, 5/8.

Sample Input 3

20 4 15
10232310010022312313

Sample Output 3

34.068777543023
27.854472795592
22.354635768263
28.066210471955

Problem Statement

In 2212, competitive programming is much more famous than now, and International Olympiad of Informatics (IOI) is one of the most famous contest in the world.

This year, N contestants, whose ID is numbered from 1 to N, participated in IOI.

The competition is held on 2 days as follows:

• Day 1: There is a paper test. Contestant i got A_i points. It is guaranteed that A_i \neq A_j (1 \leq i < j \leq N).
• Day 2: There is a practical test. In this test, score between 1 and N will be granted for each contestant. The contestant who performed the best will get N points, the contestant who performed the second best will get N - 1 points, ..., and the contestant who performed the worst will get 1 points.

Currently, you knows Day-1 score of all participants. But you don't know any of Day-2 results.
In IOI-rule, the participants' final score is (the score of paper test) + (the score of practical test).

The rank of the contestant will be determined as follows:

• Basically, the higher the final score is, the higher the rank is. (Note: The highest rank is 1, and the lowest rank is N.)
• If there are tie score, the rank will be determined with random-lottery among the contestant who got the same score.

In addition, contestant who got rank 1 will get a gold medal, contestant who got rank 2 will get a silver medal, and contestant who got rank 3 will get a bronze medal.

He knows one more informations about the final standings in IOI 2212. The information is represented as one integer P (either 1 or 2).

• Let X be the participant ID who got the gold medal.
• Let Y be the participant ID who got the silver medal.
• Let Z be the participant ID who got the bronze medal.
• If P = 1, A_X > A_Y > A_Z is satisfied.
• If P = 2, A_X > A_Z > A_Y is satisfied.

How many possible combinations of (X, Y, Z) are there?

Constraints

• N is an integer between 5 and 1 \ 000 \ 000 (inclusive)
• P is either 1 or 2
• A_i is an integer between 1 and 1 \ 000 \ 000 \ 000 (inclusive)
• All A_i are different.

Subtasks and scoring

In this problem, there are 2 subtasks as follows.

1. (600 points)：P = 1
2. (600 points)：P = 2

In each subtask, there are 12 datasets as follows.

1. (50 points)：5 \leq N \leq 7
2. (50 points)：5 \leq N \leq 15
3. (50 points)：5 \leq N \leq 30
4. (50 points)：5 \leq N \leq 70
5. (50 points)：5 \leq N \leq 200
6. (50 points)：5 \leq N \leq 600
7. (50 points)：5 \leq N \leq 2 \ 000
8. (50 points)：5 \leq N \leq 8 \ 000
9. (50 points)：5 \leq N \leq 50 \ 000
10. (50 points)：5 \leq N \leq 200 \ 000
11. (50 points)：5 \leq N \leq 500 \ 000
12. (50 points)：5 \leq N \leq 1 \ 000 \ 000

Note: In each datasets, there can be two or more testcases.

Sample Input 1

5 1
3 1 6 4 8

Sample Output 1

4

Let B_i be the Day-2 score of contestant i.
There are 4 ways as follows. X is the ID of gold medalist, Y ID the id of silver medalist, and Z is the ID of bronze medalist.

• (X, Y, Z) = (5, 3, 1). If B = (3, 4, 2, 1, 5), the final score will be 6, 5, 8, 5, 13. Therefore, it satisfies the condition.
• (X, Y, Z) = (5, 3, 2). If B = (2, 4, 3, 1, 5), the final score will be 5, 5, 9, 5, 13. Therefore, depending on lottery, it is possible that satisfies the condition.
• (X, Y, Z) = (5, 3, 4). If B = (1, 2, 3, 4, 5), the final score will be 4, 3, 9, 8, 13. Therefore, it satisfies the condition.
• (X, Y, Z) = (5, 4, 1). If B = (4, 2, 1, 3, 5), the final score will be 7, 3, 7, 7, 13. Therefore, depending on lottery, it is possible that satisfies the condition.

Sample Input 2

5 2
6 4 1 7 2

Sample Output 2

3

There are 3 ways as follows.

• (X, Y, Z) = (4, 2, 1). If B = (1, 5, 3, 4, 2), the final score will be 7, 9, 4, 11, 4. Therefore, it satisfies the condition.
• (X, Y, Z) = (4, 5, 1). If B = (1, 2, 3, 4, 5), the final score will be 7, 6, 4, 11, 7. Therefore, depending on lottery, it is possible that satisfies the condition.
• (X, Y, Z) = (4, 5, 2). If B = (1, 3, 2, 4, 5), the final score will be 7, 7, 3, 11, 7. Therefore, depending on lottery, it is possible that satisfies the condition.

Sample Input 3

10 1
6 4 11 14 3 17 13 18 8 10

Sample Output 3

26

Sample Input 4

10 2
18 14 19 4 12 1 7 15 9 5

Sample Output 4

14

Problem Statement

E869120 the Coder decided to give a sequence to square1001 as a birthday gift each year, for next Q years.
Since square1001 said that "It is better if the length of sequence is shorter", the length of the sequence should be as short as possible.
Moreover, there is "AtCoder's Percepts" which has been told from ancient times, so he also decided to determine the sequence based on this percepts.

The contents of "AtCoder percepts" is as follows:

• The elements in sequence should be distinct.
• The sequence which is about to give, should have exactly K increasing subsequence. (K is "holy number")
• Subsequence of A = (A_1, A_2, ..., A_N) is the sequence which can make by deleting some (possibly zero or all) elements without changing the order of remaining elements.
• Note: Also empty sequence is included as a increasing subsequence. In addition, even if the places which has deleted is different, when the resulting subsequence is same, it is regarded as the same subsequence.
• For example, if A = (3, 4, 1, 2), there are 7 increasing subsequences: (), (1), (2), (3), (4), (1, 2), (3, 4).

In AtCoder, "holy number" will change every year. In i-th year, holy number is K_i.
Please find a sequence which E869120 the Coder should give as a present in each year.

Input

Input is given from Standard Input in the following format:

Q
K_1
K_2
K_3
...
K_Q

Output

Print Q lines as follows:

(Information of sequence in 1-st year)
(Information of sequence in 2-nd year)
(Information of sequence in 3-rd year)
...
(Information of sequence in Q-th year)

You should output the information of sequence as follows:

N A_1 A_2 A_3 ... A_N

Note N is the length of A.
The sequence should satisfy these conditions:

• 0 \leq N \leq 128
• 0 \leq A_i \leq 999
• A_i \neq A_j (i \neq j)

Sample Input 1

2
5
10

Sample Output 1

3 2 3 1
6 8 6 9 1 2 0

The sequence that E869120 gives in 1st year is (2, 3, 1).
There are 5 increasing subsequence: (), (1), (2), (3), (2, 3).

Sample Input 2

3
20
100
869120

Sample Output 2

9 9 7 3 6 5 8 4 1 2
10 0 5 9 3 6 1 4 2 7 8
72 47 45 28 9 41 50 33 61 27 15 38 54 52 22 57 7 30 12 46 21 19 8 71 20 23 6 18 26 17 39 4 53 44 3 31 68 29 42 62 37 69 67 40 65 2 55 36 35 11 49 24 25 43 48 0 1 16 10 70 66 64 32 5 51 60 63 58 56 59 13 14 34

Problem Statement

June 20th, 2022 is the day of 10 year anniversary from the launch of AtCoder.
On this day, a garden was built in front of AtCoder to celebrate this anniversary.

The garden is represented as a H \times W grid. The cell that i-th row from the top and the j-th column from the left is denoted as cell (i, j).
In each cell, there is a flower. The beauty of flower in cell (i, j) is A_{i, j}.

An example of the garden is as follows: (The case of H = 4, W = 5)

You should make a beautiful garden by cutting flowers in some cells. The condition which should satisfy to be a beautiful garden is as follows:

• For all a, b, c, d that both flowers in cell (a, b) and cell (c, d) ((a, b) \neq (c, d)) has not been cut, it satisfies following condition.
• From (a, b) to (c, d), there is exactly 1 ways to go, by moving either of up, right, left, down by one square repeatedly, without passing the same cell twice.

For example, if you cut some flowers like A, and B, it will be a beautiful garden.

For example, if you cut some flowers like C, D, E, it will not be a beautiful garden.

The score of garden will be calculated as follows:

• If the garden is not a beautiful garden, the score will be 0.
• If the garden is a beautiful garden, the score will be the total beuaty of flowers which has not been cut.

For example, the score of garden A is 20, the score of garden B is 60, and the score of garden C, D, E are 0.
Print a way of cutting flowers that score of garden is as high as you can.

Input

Input is given from Standard Input in the following format:

H W
A_{1, 1} A_{1, 2} A_{1, 3} ... A_{1, W}
A_{2, 1} A_{2, 2} A_{2, 3} ... A_{2, W}
A_{3, 1} A_{3, 2} A_{3, 3} ... A_{3, W}
...
A_{H, 1} A_{H, 2} A_{H, 3} ... A_{H, W}

Output

Print H likes as follows:

c_{1, 1}c_{1, 2}c_{1, 3} ... c_{1, W}
c_{2, 1}c_{2, 2}c_{2, 3} ... c_{2, W}
c_{3, 1}c_{3, 2}c_{3, 3} ... c_{3, W}
...
c_{H, 1}c_{H, 2}c_{H, 3} ... c_{H, W}

c_{i, j} should be # if you won't cut a flower in cell (i, j), and . if you will cut flower in cell (i, j).

Subtasks and Scoring

There are 15 testcases that are used for grading. Since max score per each case is 100. Max score of this problem is 100 \times 15 = 1500.
For each case, it will be graded as follows. Let L be the score of garden in your output, and let L' be L \div (H \times W).

(i) When H = 5, W = 5 (Case #1, #2, #3), or H = 5, W = 500 (Case #4, #5, #6):

• If 0.00 \leq L' < 2.00 : 0 points
• If 2.00 \leq L' < 3.33 : 0 + (L - 2.00) \times 21 points
• If 3.33 \leq L' < 3.93 : 28 + (L - 3.33) \times 40 points
• If 3.93 \leq L' < 4.03 : 52 + (L - 3.93) \times 480 points
• If 4.03 \leq L' : 100 points

(ii) When H = 500, W = 500 (Case #7, #8, #9, #10, #11, #12, #13, #14, #15):

• If 0.00 \leq L' < 2.00 : 0 points
• If 2.00 \leq L' < 3.33 : 0 + (L - 2.00) \times 21 points
• If 3.33 \leq L' < 3.78 : 28 + (L - 3.33) \times 75 points
• If 3.78 \leq L' < 3.84 : 61 + (L - 3.78) \times 650 points
• If 3.84 \leq L' : 100 points

This is the graph which describes the relation between L' and score when 2.00 \leq L' \leq 4.05.

Note

The verdict will be AC if there is no testcase which is graded 0 points.
It means it is not always full-score if you got AC, and it also means even if you got WA it is possible that you got some partial score.

Since this problem is marathon-match like optimization task, it is not guaranteed that there is a full-solution for all cases. Solution of problemsetter is not always full score. In addition, it is very unlikely, but if many people wrote the solution which significantly over the creterion of full score, changing scoring formula is also possible. It is guaranteed that there is no change of scoring formula after 3 hours from the beginning of this contest.

Sample Input 1

3 3
1 2 3
4 5 6
7 8 9

Sample Output 1

#.#
###
#.#

In this example, the score of garden is 1 + 3 + 4 + 5 + 6 + 7 + 9 = 35.
Note: This input is not included in datasets for grading.

Sample Input 2

4 5
4 1 8 2 6
2 2 1 2 5
3 5 1 9 2
5 1 2 3 6

Sample Output 2

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

This example is as same as the example picture that written in problem statement.
Also, this sample output is as same as garden B that written in problem statement. The score of garden is 60, and value of L' is 3.0.
Actually, there is a solution which the score of garden is 62 :)
Note: This input is also not included in datasets for grading.