Little Q is a diligent elementary school student whose dream is to enter his favorite university to study computer science. To achieve this goal, he has been studying the basics of informatics competitions since he was young.

Today, Little Q learned about the XOR operation. To test whether he has mastered it, he decided to create a problem for himself. He randomly generated a sequence $X = \{x_1, x_2, \dots, x_n\}$ and a sequence $Y = \{y_1, y_2, \dots, y_m\}$. For every pair $(x_i, y_j)$ from sequences $X$ and $Y$, Little Q calculates their bitwise XOR result and fills it into the $i$-th row and $j$-th column of a matrix $A$, such that: $$A_{ij} = x_i \oplus y_j$$

After obtaining this $n \times m$ matrix $A$, Little Q needs to verify if his calculations are correct. Verifying all XOR results is too tedious, so he thought of a simpler verification method. He selects a rectangular region in matrix $A$ and finds the $k$-th largest number in this region. If this number matches the standard answer, the test is passed. Little Q performs $p$ such tests in total. If all $p$ tests are passed, he considers the calculated matrix $A$ to be basically correct.

However, Little Q does not have the standard answers. Therefore, he asks for your help, hoping you can write a program to calculate the standard answer for each test.

Input

The first line contains two positive integers $n, m$, representing the lengths of the two sequences, respectively. The second line contains $n$ non-negative integers $x_i$, as described in the problem statement. The third line contains $m$ non-negative integers $y_j$, as described in the problem statement. The fourth line contains a positive integer $p$, representing the number of tests. The following $p$ lines each contain five positive integers describing a test. Specifically, the first four integers in the $i$-th line are $U_i, D_i, L_i, R_i$, representing the upper, lower, left, and right boundaries of the $i$-th test region (the rectangular region includes the boundaries). The fifth integer is $K_i$, representing that the test is for the $K_i$-th largest number in this rectangular region.

Output

There are $p$ lines, each containing only one non-negative integer, representing the standard answer for that test.

Examples

Input 1

3 3
1 2 4
7 6 5
3
1 2 1 2 2
1 2 1 3 4
2 3 2 3 4

Output 1

6
5
1

Note

The matrix obtained by calculation is as follows:

The first search finds the 2nd largest value in (6, 7, 5, 4), the answer is 6. The second search finds the 4th largest value in (6, 7, 4, 5, 4, 7), the answer is 5. The third search finds the 4th largest value in (4, 7, 2, 1), the answer is 1.

Constraints

For all test data, it is satisfied that: $1 \le U_i \le D_i \le n \le 1000$; $1 \le L_i \le R_i \le m \le 300,000$; $0 \le x_i, y_j < 2^{31}$; $1 \le K_i \le (D_i - U_i + 1) \times (R_i - L_i + 1)$; $1 \le p \le 500$.

Among them, some test data have the following characteristics (not mutually inclusive): For 5% of the data, $1 \le m \le 1,000$, $1 \le p \le 10$, $K_i = 1$; For 15% of the data, $1 \le m \le 3,000$, $1 \le p \le 200$; For 20% of the data, $p = 1$; For 30% of the data, $K_i = 1$; * For the remaining 30% of the data, there are no other characteristics.