셔플 기계

태준이는 친구들과 카드 게임을 즐기려고 카드 셔플 기계를 구입했다. 모든 게임에서 이기고 싶었던 태준이는 기계의 구조를 분석해서 셔플 결과를 예측하려고 한다.

셔플 기계에는 $M$가지의 셔플 기술이 내장되어 있다. $i$번째 셔플 기술은 $1$부터 $N$까지 각 수가 정확히 한 번씩 등장하는 길이 $N$의 수열 $S_i$로 표현된다. $i$번째 셔플 기술을 $1$번 실행하면, 위에서 $j$번째에 있는 카드는 위에서 $S_{ij}$번째에 위치하게 된다.

셔플 기계를 작동시키면 $K$번의 셔플을 정해진 순서대로 실행한 후 종료된다. 한 번의 셔플은 $X_i$와 $Y_i$ 두 개의 정수로 표현되며, 이는 $X_i$번 셔플 기술을 $Y_i$번 실행한다는 뜻이다.

처음에 카드는 위에서부터 $1$번부터 $N$번까지 순서대로 정렬되어 있다. 셔플 기계를 작동시킨 후 카드들이 어떻게 배열되는지 찾아보자.

첫 번째 줄에 $N$, $M$, $K$가 공백으로 구분되어 주어진다.

다음 $M$개의 줄 중 $i$번째 줄에는 $i$번째 셔플 기술을 나타내는 $S_{i1}, S_{i2}, \cdots, S_{iN}$이 차례대로 공백으로 구분되어 주어진다.

다음 $K$개의 줄 중 $i$번째 줄에는 $i$번 셔플에서 실행할 셔플 기술의 번호 $X_i$와 해당 기술을 실행할 횟수 $Y_i$가 공백으로 구분되어 주어진다.

셔플 기계를 작동시킨 후 카드의 최종 순서를 위에서부터 순서대로 출력한다.

• 주어지는 모든 수는 정수이다.
• $2 \leq N \leq 1\,000$
• $1 \leq M \leq 1\,000$
• $1 \leq K \leq 1\,000$
• $S_{i1}, S_{i2}, \cdots, S_{iN}$에는 $1$부터 $N$까지의 수가 정확히 한 번씩 등장한다. ($1 \leq i \leq M$)
• $1 \leq X_i \leq M$ ($1 \leq i \leq K$)
• $1 \leq Y_i \leq 10^9$ ($1 \leq i \leq K$)