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

제한

힌트