30042번 - Function Box

문제

$N$ 개의 함수 상자가 있다. 각 함수 상자에는 0ドル$부터 $N-1$까지 번호가 부여되어 있다. 함수 상자 $i$는 $A_i$ 개의 입력 단자와 $B_i$ 개의 출력 단자를 가진다. 각 단자에는 0ドル$부터 차례대로 번호가 부여되어 있다.

기본적으로 함수 상자는 다음과 같이 직사각형 형태로 생겼다. 함수 상자의 둘레는 문자 -, |, +로 표현되고, 내부에는 번호를 의미하는 하나의 수가 적혀있다. 각 함수 상자의 내부에는 수가 정확하게 하나 적혀 있으며, 이 수의 숫자는 모두 하나의 행에 연속해 있다.

...........
.+-------+.
.|.......|.
.|..610..|.
.|.......|.
.+-------+.
...........

위의 경우에는 입력 단자와 출력 단자가 없다. 입력 단자와 출력 단자는 문자 >, ^, <, v로 표시한다. 문자의 좁은 쪽 방향이 함수 상자를 가리키면 입력 단자를, 함수 상자를 등지고 있으면 출력 단자를 나타낸다. 함수 상자의 꼭짓점에 단자가 있는 경우는 없다. 즉, 함수 상자의 네 꼭짓점을 나타내는 문자는 항상 +다.

예를 들어, 함수 상자 3ドル$이 $A_3=7$ 개의 입력 단자, $B_3=3$ 개의 출력 단자를 가진다면, 다음과 같이 나타낼 수 있다.

...........
.+-vv-^--+.
.<.....3.<.
.>.......|.
.|.......>.
.+-^---^^+.
...........

단자의 번호는 다음과 같이 알아낼 수 있다. 함수 상자의 왼쪽 위 꼭짓점에서 시작하여 시계 방향으로 둘레를 따라가면서 만나는 입력 단자와 출력 단자 각각에 0ドル$부터 차례대로 수를 부여하자. 이 수가 그 단자의 번호이다. 예를 들어, 위의 경우, 함수 상자 3ドル$의 입력 단자 3ドル$와 출력 단자 2ドル$를 나타내는 문자는 각각 ^, <이다.

입력 단자와 출력 단자는 하나의 선으로 이어줄 수 있다. 선은 다음과 같이 교차하거나 중간에 갈라지고 합쳐지지 않는 닫힌 선의 형태를 가지며, 문자 -, |, +로 표현된다.

........
..+--+..
..+-+|..
.+--+|..
.|...+-.
........

함수 상자 $a$의 출력 단자를 함수 상자 $b$의 입력 단자에 연결했다면, $a<b$임이 보장된다. 또한, 어떤 두 단자가 연결되어 있다면, 그 둘 중 하나는 입력 단자, 다른 하나는 출력 단자임이 보장된다.

예를 들어, 다음 그림에는 네 개의 함수 상자가 있고, 모든 선의 연결 상태를 표현하면 이러하다.

............
.+v+........
.<0>+...+-+.
.+^+|+-->.<.
....++.+<1>.
...+--+|+-+.
...|..++....
...|........
.+-v^-+.....
.|....|+v+..
.<.2..>>3|..
.+-v--+|.>..
.......+^+..
............

• 함수 상자 0ドル$의 출력 단자 0ドル$을 함수 상자 1ドル$의 입력 단자 1ドル$에 연결.
• 함수 상자 1ドル$의 출력 단자 1ドル$을 함수 상자 2ドル$의 입력 단자 0ドル$에 연결.
• 함수 상자 2ドル$의 출력 단자 1ドル$을 함수 상자 3ドル$의 입력 단자 2ドル$에 연결.

예시에서 마지막 연결의 표현 방법을 유의하라. 선끼리, 혹은 함수 상자끼리는 서로 교차하거나 영역을 공유하지 않는다.

그림에서 문자 +는 모호하게 사용되지 않는다. 엄밀하게 말하자면, 함수 상자의 모서리에 놓이지 않은 각 문자 +에 대해 다음 조건 중 적어도 하나를 만족하는 문자가 정확하게 두 개다.

• 상하좌우로 인접한 +.
• 상하로 인접한 |, v, ^.
• 좌우로 인접한 -, >, <.

모든 함수 상자의 입력과 출력은 문자열이다. 함수 상자 $i$의 입력 단자 $j$에 주어지는 문자열이 $\text{IN}_{i,j}$라고 하자. 입력 단자에 어떠한 단자도 연결되어 있지 않다면, 빈 문자열이 주어진다고 생각한다. 먼저, 다음 과정을 통해 중간 문자열 $\text{PROC}_i$를 만든다. 이 과정은 길이 $C_i$의 수열 $D_{i,0},D_{i,1},\cdots ,D_{i,C_i-1}$에 의존한다.

1. 초기에 문자열 $\text{PROC}_i$는 빈 문자열이다.
2. 각 $j=0,1,\cdots ,C_i-1$에 대해 차례대로 다음을 수행한다:
   1. 만약 문자열 $\text{IN}_{i,D_{i,j}}$가 비어있다면, 과정 2.로 넘어간다.
   2. 문자열 $\text{IN}_{i,D_{i,j}}$의 가장 앞 문자 $c$를 뽑는다. 이 문자열의 길이는 1ドル$ 줄어든다.
   3. 문자열 $\text{PROC}_i$의 끝에 문자 $c$를 추가한다. 이 문자열의 길이는 1ドル$ 늘어난다.
3. 과정 2.를 충분히 많이 반복한다. 문자열 $\text{PROC}_i$가 수렴하면 과정을 종료한다.

출력 또한 길이 $E_i$의 수열 $F_{i,0},F_{i,1},\cdots ,F_{i,E_i-1}$에 의존한다. 출력 단자 $j$에 출력할 문자열 $\text{OUT}_{i,j}$는 다음과 같이 결정된다.

1. 초기에 각 문자열 $\text{OUT}_{i,j}$는 빈 문자열이다.
2. 각 $j=0,1,\cdots ,E_i-1$에 대해 차례대로 다음을 수행한다:
   1. 만약 문자열 $\text{PROC}_i$가 비어있다면, 과정을 종료한다.
   2. 문자열 $\text{PROC}_i$의 가장 앞 문자 $c$를 뽑는다. 이 문자열의 길이는 1ドル$ 줄어든다.
   3. 문자열 $\text{OUT}_{i,F_{i,j}}$의 끝에 문자 $c$를 추가한다. 이 문자열의 길이는 1ドル$ 늘어난다.
3. 과정 2.를 충분히 많이 반복한다. 문자열 $\text{PROC}_i$가 빈 문자열이 되면, 종료한다.

예외적으로, 함수 상자 0ドル$의 출력은 다음과 같이 결정한다. 먼저, 알파벳으로 이루어진 $K$ 개의 문자열 $S_0,S_1,\cdots ,S_{K-1}$을 잡는다. 단, 문자열 $S_i$에서 정수 0ドル\le n\le i-1$에 대해, “($n$)”의 표현을 사용할 수 있다. 이는 이 부분을 문자열 $S_n$으로 대치하라는 뜻이다.

예를 들어, $S_0,ドル $S_1,ドル $S_2$가 다음과 같이 주어졌다고 하자.

• $S_0=$ “Good”
• $S_1=$ “(0)Day(0)Night”
• $S_2=$ “Hello(1)(0)ByeGood”

각 문자열이 실제로 의미하는 값은 아래와 같다.

• $\text{actual}\left( S_0 \right) =$ “Good”
• $\text{actual}\left( S_1 \right) =$ “GoodDayGoodNight”
• $\text{actual}\left( S_2 \right) =$ “HelloGoodDayGoodNightGoodByeGood”

함수 상자 0ドル$의 출력 단자 $i$에 출력되는 문자열은 $\text{actual}\left( S_{G_i} \right)$와 같다.

이제, $Q$ 개의 쿼리가 주어진다. $i$ 번째 쿼리에서 여러분은 함수 상자 $Y_i$의 출력 단자 $O_i$에서 출력되는 문자열 $\text{OUT}_{Y_i,O_i}$의 $P_i$ 번째 문자를 알아내야 한다.

입력

첫 번째 줄에 두 정수 $H,ドル $W$가 주어진다. 그다음 줄부터 $H$ 개의 줄에 걸쳐, $N$ 개의 함수 상자가 모두 그려진 $H\times W$의 그림이 문자열 형식으로 주어진다.

그다음 줄에 $N$ 이상의 정수 $N'$이 주어진다. 그다음 줄부터 $N'$ 개의 줄에 걸쳐, 수열 $D_i$가 주어진다. 이 중 $i+1$ 번째 줄에는 $C_i+1$ 개의 정수 $C_i,ドル $D_{i,0},\cdots ,D_{i,C_i-1}$가 차례대로 주어진다. 그다음 줄부터 $N'$ 개의 줄에 걸쳐, 수열 $F_i$가 주어진다. 이 중 $i+1$ 번째 줄에는 $E_i+1$ 개의 정수 $E_i,ドル $F_{i,0},\cdots ,F_{i,E_i-1}$가 차례대로 주어진다.

그다음 줄에 정수 $K$가 주어진다. 그다음 줄부터 $K$ 개의 줄에 걸쳐, 문자열 $S_i$가 주어진다. 이 중 $i+1$ 번째 줄에는 문자열 $S_i$가 주어진다.

그다음 줄에 $B_0$ 이상의 정수 $M'$이 주어진다. 그다음 줄에 $M'$ 개의 정수 $G_0,G_1,\cdots ,G_{M'-1}$가 차례대로 주어진다.

그다음 줄에 정수 $Q$가 주어진다. 그다음 줄에 $Q$ 개의 정수 $Y_1,\cdots ,Y_Q$가 주어진다. 그다음 줄에 $Q$ 개의 정수 $O_1,\cdots ,O_Q$가 주어진다. 그다음 줄에 $Q$ 개의 정수 $P_1,\cdots ,P_Q$가 주어진다.

출력

첫 번째 줄에 길이 $Q$의 문자열을 출력한다.

이 문자열의 $i$ 번째 문자는 아래와 같아야 한다.

• 문자열 $\text{OUT}_{Y_i,O_i}$의 길이가 $P_i$ 이상이라면, 그 문자열의 $P_i$ 번째 문자여야 한다.
• 문자열의 길이가 $P_i$ 미만이라면, !여야 한다.

제한

• 3ドル\le H \le 50$
• 3ドル\le W \le 50$
• 1ドル\le N\le N'\le 300$
• 1ドル\le A_i$ $(0\le i\le N-1)$
• 1ドル\le B_i$ $(0\le i\le N-1)$
• $A_i=B_i=10^9$ $(N\le i\le N'-1)$
• 1ドル\le C_i \le 15$ $(0\le i\le N'-1)$
• 1ドル\le E_i \le 15$ $(0\le i\le N'-1)$
• 0ドル\le D_{i,j} \le A_i - 1$ $(0\le i\le N'-1;0\le j\le C_i-1)$
• 0ドル\le F_{i,j} \le B_i - 1$ $(0\le i\le N'-1;0\le j\le E_i-1)$
• 1ドル\le K \le 50$
• 1ドル\le\left| S_i \right|\le 50$ $(0\le i\le K-1)$
• $B_0\le M'\le 200$
• 0ドル\le G_i\le K-1$ $(0\le i\le M'-1)$
• 1ドル\le Q\le 1,円 000$
• 0ドル\le Y_i\le N-1$ $(1\le i\le Q)$
• 0ドル\le O_i\le B_{Y_i}-1$ $(1\le i\le Q)$
• 1ドル\le P_i\le 10^{18}$ $(1\le i\le Q)$
• 주어지는 그림은 문자 ., -, |, +, >, <, ^, v, 0, ..., 9로만 이루어진, $N$ 개의 함수 상자가 모두 그려진 올바른 그림이다.
• 그림에는 $N$ 개의 함수 상자와 선 외에는 다른 불필요한 요소가 그려져 있지 않다.
• 모든 문자 +는 진행 방향이 변할 때에만 사용된다.

힌트