Description

There is a row with N blocks. Blocks are numbered from left to right in 1-based indexing. The value of the i-th block is a_i.

You are on the 1-th blocks now. For convenience, let's call the block you currently on as happy block. Of course you can only be on one block at the same time.

Now you need to execute Q operations. There are three kinds of operations:

1. Move to the blocks which is on the left/right to happy block.
2. Output the value of happy block.
3. Remove the block in the middle of all the blocks. If there are not only one blocks in the middle(i.e the number of blocks is an even number), remove the one which is closer to the left side. If the removed block is happy block, you would move to the block which is on the right to happy block before removing.

It's guaranteed that:

1. The block you move to must exist.
2. The third type of operations appears at most N - 1 times(i.e there must be at least one block all the time).

Note: be careful of the efficiency of your strategy.

Input

The first line contains one integer N (1 ≤ N ≤ 5 x 10⁵) – the number of blocks.

The second line contains N integers a₁, a₂, ..., a_N (0 ≤ a_i ≤ 10⁹) – the value of each block.

The third line contains one integer Q (1 ≤ Q ≤ 5 x 10⁵) – the number of operations you need to execute.

Then Q lines follow. The i+3-th line contains one integer type_i (1 ≤ type_i ≤ 3) – the type of operations you need to execute. If type_i = 1 then one integer dir (dir = -1 or dir = 1) follows – -1 for moving to the block which is on the left to happy block and 1 for the right.

 

It's guaranteed that:

• The 1st testcase must be as same as Sample below
• For the first five testcases: 1 ≤ N, Q ≤ 1000

Output

For every 2nd type operations, output the value of happy block then.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss