두 수열

두 수열 $X_1, \cdots, X_s$와 $Y_1, \cdots, Y_t$가 주어진다. 비어 있는 수열 $S$에서 시작하여 시행을 정확히 $s+t$번 반복한다. 최종 상태의 $S$가 될 수 있는 수열 중 사전순으로 가장 빠른 것을 $X \star Y$로 정의한다.

시행은 다음 두 행동 중 하나이다.

• $X$가 비어 있지 않으면, $X$의 맨 앞 원소를 제거하고 $S$의 맨 뒤에 추가한다.
• $Y$가 비어 있지 않으면, $Y$의 맨 앞 원소를 제거하고 $S$의 맨 뒤에 추가한다.

길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$과 길이가 $M$인 정수 수열 $B_1, B_2, \cdots, B_M$이 주어진다.

다음 쿼리를 처리하는 프로그램을 작성하시오.

• a b k: $A[1..a] \star B[1..b]$의 $k$번째 수를 출력한다.

첫째 줄에 $N$, $M$, $Q$가 공백으로 구분되어 주어진다. ($1\le N,M,Q\le 100\,000$)

둘째 줄에 $A_1$, $A_2$, $\cdots$, $A_N$이 공백으로 구분되어 주어진다. ($1\le A_i\le 10^9$)

셋째 줄에 $B_1$, $B_2$, $\cdots$, $B_M$이 공백으로 구분되어 주어진다. ($1\le B_i\le 10^9$)

이어서 $Q$개의 줄에 쿼리 $a$, $b$, $k$가 공백으로 구분되어 한 줄에 하나씩 주어진다. ($1\le a\le N$; $1\le b\le M$; $1\le k\le a+b$)

$Q$개의 줄에 걸쳐 각 쿼리의 답을 입력 순서대로 출력한다.