Manelzuma's Revenge

정사각형에서 시작해 $9$개의 하위 정사각형으로 나눈 뒤 가운데 하나를 비우는, 잘 알려진 프랙탈을 떠올려 보자:

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

이 연산을 남은 $8$개의 하위 정사각형 각각에 대해 다시 반복하고, 계속 이어 나간다. 다른 연산을 고르면 다른 프랙탈이 만들어진다. 예를 들어 가운데 대신 왼쪽 위와 오른쪽 아래 모서리를 비울 수도 있고, 정사각형을 다른 개수의 하위 정사각형으로 나눌 수도 있다.

여기서는 프랙탈 연산을 $n \times n$ 문자 격자로 지정하며, 각 문자는 대응하는 하위 정사각형에 특정한 치환을 수행한다:

• . (마침표): 하위 정사각형이 완전히 비워진다.
• ! (느낌표): 하위 정사각형이 가득 차며, 더 이상 연산의 대상이 되지 않는다.
• ? (물음표): 하위 정사각형이 가득 찬 채로 남으며, 이후 연산의 대상이 된다.

위 프랙탈은 다음 $3 \times 3$ 격자로 표현된다:

???
?.?
???

$2 \times 2$ 격자

.!
?.

로 정의된 프랙탈을 네 번 반복하면 다음과 같다(반복 $1$회부터 $4$회까지):

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

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

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

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

여러분의 임무는 $n \times n$ 격자로 지정된 임의의 프랙탈의 한 영역을 출력하는 것이다. 이 프랙탈들은 전체를 메모리에 담기에는 너무 커지므로, 출력할 부분만 계산해야 한다.

첫째 줄에 양의 정수 $n$ ($1 \le n \le 100$)이 주어진다. 다음 $n$개의 줄에는 각각 ., !, ? 중 하나로 이루어진 $n$개의 문자가 주어지며, 이는 반복할 프랙탈 연산을 정의한다.

이후 입력은 프랙탈의 영역에 대한 질의들로 이루어진다. 각 질의는 두 줄로 주어진다:

• 첫째 줄에는 물체에 적용할 반복 횟수 $k$가 주어진다. 반복 $0$회는 크기가 $n^k \times n^k$인 완전히 채워진 정사각형이며, 따라서 $k$번 반복한 뒤 전체 물체의 크기는 $n^k \times n^k$이다.
• 둘째 줄에는 네 정수 $b$, $t$, $l$, $r$이 주어지며, 각각 출력할 영역의 아래 행, 위 행, 왼쪽 열, 오른쪽 열을 뜻한다.

행은 아래에서 위로 $1$부터, 열은 왼쪽에서 오른쪽으로 $1$부터 번호가 매겨진다. 입력은 $k$ 자리에 -1이 적힌 줄로 끝난다.

제약: $k \le 100$이며, $b$, $t$, $l$, $r$은 각각 백만 이하이고, 출력할 영역의 너비와 높이는 각각 $100$ 이하이다.

각 질의에 대해 요청된 영역을 한 줄에 한 행씩, 위 행을 먼저, 아래 행을 마지막에 출력한다. 채워진 칸은 *로, 빈 칸은 공백으로 출력하고, 출력이 정사각형에 가깝게 보이도록 한 행 안의 인접한 칸 사이에는 공백 하나를 둔다. 각 영역을 출력한 뒤에는 빈 줄을 하나 남긴다.