30182번 - 두 수열

두 수열 $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$개의 줄에 걸쳐 쿼리에 대한 답을 순서대로 출력한다.