# Fractal pictures P93774

Statement

thehtml

Let P be a rectangular pattern with n rows and m columns, where each position is either empty or marked. We can use P to make nice fractal pictures as follows: Start with a 1 × 1 picture, with its position marked. Then, do k times: Replace every marked position by P, and every empty position by an empty n × m grid. At the end of this process we get an nk × mk fractal picture. Here, you will have to print fractal pictures, and also answer some questions about them.

Input

Input consists of several cases separated with blank lines. Each case starts with a line with ‍n and m. Then follows P in n lines, each with m characters: ‘.’ for an empty position, ‘X’ for a marked position. Then follows a line with k, a line with an integer q ≥ 1, and q lines, each with a query: every line 1 ≤ iq contains three integers ki, ri and ci. Assume 2 ≤ n ≤ 20, 2 ≤ m ≤ 20, nk ≤ 80, mk ≤ 80, 1 ≤ rinki ≤ 1016, 1 ≤ cimki ≤ 1016.

Output

For every test case in the input, print first the nk × mk fractal picture that results after applying k times the pattern P. Then print a blank line, followed by q lines, one for each query in the input. For every i, print the content of the (ri, ci) position after ki steps, following the format of the sample output. Print a blank line after the output for every test case.

Public test cases
• Input

3 3
.X.
XXX
.X.
3
2
3 1 14
3 1 15

2 3
..X
XXX
2
4
2 1 1
2 1 9
2 4 1
0 1 1

2 2
.X
XX
3
1
50 1125899906842624 1125899906842624

Output

.............X.............
............XXX............
.............X.............
..........X..X..X..........
.........XXXXXXXXX.........
..........X..X..X..........
.............X.............
............XXX............
.............X.............
....X........X........X....
...XXX......XXX......XXX...
....X........X........X....
.X..X..X..X..X..X..X..X..X.
XXXXXXXXXXXXXXXXXXXXXXXXXXX
.X..X..X..X..X..X..X..X..X.
....X........X........X....
...XXX......XXX......XXX...
....X........X........X....
.............X.............
............XXX............
.............X.............
..........X..X..X..........
.........XXXXXXXXX.........
..........X..X..X..........
.............X.............
............XXX............
.............X.............

after 3 step(s), (1, 14) is marked
after 3 step(s), (1, 15) is empty

........X
......XXX
..X..X..X
XXXXXXXXX

after 2 step(s), (1, 1) is empty
after 2 step(s), (1, 9) is marked
after 2 step(s), (4, 1) is marked
after 0 step(s), (1, 1) is marked

.......X
......XX
.....X.X
....XXXX
...X...X
..XX..XX
.X.X.X.X
XXXXXXXX

after 50 step(s), (1125899906842624, 1125899906842624) is marked

• Information
Author