Despite everything going on in the world, you must still attend online school. Alas, you find yourself in a Zoom call about PHE. Due to the obvious, you become bored and start to think about the upcoming classes in the day. Your next class is coding. Your teacher, Dr. Bruce, has an interesting way to keep students focused. He will generate values using his method way to determine which kids to call on.

Your class contains ~N~, people. He chooses a value by creating two arrays ~x~ and ~y~ of length ~N~. Then, he fills the arrays with his favourite positive integers in the range ~[1,10^9]~. From there, he generates an ~N~ by ~N~ grid ~G~ such that ~G_{i,j} = \max(x_j,y_i)~.

After, he will determine who to call on using one of the following queries:

1 w: Find the maximum element of column ~w~.

2 w: Find the minimum element of column ~w~.

3 w: Find the maximum element of row ~w~.

4 w: Find the minimum element of row ~w~.

You will be given all these values and ~Q~ queries in the form above.

Input Specification

The first line of input will contain positive integer ~N~.

The second line of input will contain array ~x~ of length ~N~ with each element separated by a space.

The third line of input will contain array ~y~ of length ~N~ with each element separated by a space.

The fourth line of input will contain positive integer ~Q~.

The next ~Q~ lines will contain a query in one of the four forms listed above.

Output Specification

On the ~i^\text{th}~ line, output the answer to the ~i^\text{th}~ query.

Constraints

~1 \le N, Q \le 10^6~

~1 \le x_i, y_i \le 10^9~

~1 \le w \le N~

Note that you will NOT be required to pass all the samples to receive points.

Subtask 1 [20%]

~1 \le N, Q \le 500~

Subtask 2 [80%]

No additional constraints.

Sample Input

5
1 4 5 10 2
2 3 6 7 8
3
1 2
2 2
3 5

Sample Output

8
4
10

Explanation for Sample

The grid looks like this:

2 4 5 10 2
3 4 5 10 3
6 6 6 10 6
7 7 7 10 7
8 8 8 10 8

For the first query, the maximum element in column ~2~ is ~8~. For the second query, the minimum element in column ~2~ is ~4~. For the third and final query, the maximum element of row ~5~ is ~10~.