Fractal pictures P93774

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 \times 1$ picture, with its position marked. Then, do $k$ times: Replace every marked position by $P$, and every empty position by an empty $n \times m$ grid. At the end of this process we get an $n^k \times m^k$ 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 \ge 1$, and $q$ lines, each with a query: every line $1 \le i \le q$ contains three integers $k_i$, $r_i$ and $c_i$. Assume $2 \le n \le 20$, $2 \le m \le 20$, $n^k \le 80$, $m^k \le 80$, $1 \le r_i \le n^{k_i} \le 10^{16}$, $1 \le c_i \le m^{k_i} \le 10^{16}$.

Output

For every test case in the input, print first the $n^k \times m^k$ 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 $(r_i, c_i)$ position after $k_i$ steps, following the format of the sample output. Print a blank line after the output for every test case.