Two Sequences

Two sequences $X_1, \cdots, X_s$ and $Y_1, \cdots, Y_t$ are given. Starting from an empty sequence $S$, perform a move exactly $s+t$ times. Define $X \star Y$ as the lexicographically smallest sequence that can be the final state of $S$.

A move is one of the following two actions.

• If $X$ is not empty, remove the first element of $X$ and append it to the end of $S$.
• If $Y$ is not empty, remove the first element of $Y$ and append it to the end of $S$.

You are given an integer sequence $A_1, A_2, \cdots, A_N$ of length $N$ and an integer sequence $B_1, B_2, \cdots, B_M$ of length $M$.

Write a program that processes the following query.

• a b k: Print the $k$-th number of $A[1..a] \star B[1..b]$.

The first line contains $N$, $M$, and $Q$, separated by spaces. ($1\le N,M,Q\le 100\,000$)

The second line contains $A_1, A_2, \cdots, A_N$, separated by spaces. ($1\le A_i\le 10^9$)

The third line contains $B_1, B_2, \cdots, B_M$, separated by spaces. ($1\le B_i\le 10^9$)

Each of the next $Q$ lines contains a query $a$, $b$, and $k$, separated by spaces. ($1\le a\le N$; $1\le b\le M$; $1\le k\le a+b$)

Print $Q$ lines. Print the answer to each query in the order the queries are given.