Manelzuma's Revenge

Recall the classic fractal that starts with a filled square, divides it into $9$ sub-squares, and clears the middle one:

* * * * * * * * *
* * * * * * * * *
* * * * * * * * *
* * *       * * *
* * *       * * *
* * *       * * *
* * * * * * * * *
* * * * * * * * *
* * * * * * * * *

This operation is then repeated for each of the $8$ remaining sub-squares, and so on. Choosing a different operation gives a different fractal. For example, we could clear the upper-left and lower-right corners instead of the middle, or divide the square into a different number of sub-squares.

Here the fractal operation is given as an $n \times n$ grid of characters, where each character performs a particular substitution on the corresponding sub-square:

• . (period): the sub-square becomes completely empty.
• ! (exclamation mark): the sub-square becomes full and is not subject to further operations.
• ? (question mark): the sub-square stays full and is subject to further operations.

The fractal above is represented by the $3 \times 3$ grid:

???
?.?
???

Four iterations of the fractal denoted by the $2 \times 2$ grid

.!
?.

look like this (iteration $1$ through iteration $4$):

* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *

        * * * *
        * * * *
        * * * *
        * * * *
* * * *        
* * * *        
* * * *        
* * * *        

        * * * *
        * * * *
        * * * *
        * * * *
    * *        
    * *        
* *            
* *            

        * * * *
        * * * *
        * * * *
        * * * *
    * *        
    * *        
  *            
*              

Your task is to print a region of an arbitrary fractal specified by an $n \times n$ grid. These fractals grow far too large to store completely in memory, so you must compute only the requested region.

The first line contains a positive integer $n$ ($1 \le n \le 100$). The next $n$ lines each contain $n$ characters drawn from ., !, ?, defining the fractal operation to be iterated.

The rest of the input is a sequence of region queries. Each query is given on two lines:

• The first line contains $k$, the number of iterations applied to the object. Iteration $0$ is a completely filled square of size $n^k \times n^k$, so after $k$ iterations the whole object is $n^k \times n^k$.
• The second line contains four integers $b$, $t$, $l$, $r$: the bottom row, top row, left column, and right column of the region to print.

Rows are numbered from bottom to top starting at $1$, and columns from left to right starting at $1$. The input ends with a line containing -1 in place of a $k$ value.

Constraints: $k \le 100$; each of $b$, $t$, $l$, $r$ is at most one million; and the width and height of the region are each at most $100$.

For each query, print the requested region, one line per row, with the top row first and the bottom row last. Print * for a filled cell and a space for an empty cell, and separate adjacent cells in a row with a single space so the output looks roughly square. Print a blank line after each region.