Let median of some array be the number which would stand in the middle of this array if it was sorted beforehand. If the array has even length let median be smallest of of two middle elements. For example, median of the array [10,3,2,3,2] is 3 (i.e. ). Median of the array [1,5,8,1] is 1 (i.e. ).

At first, you're given an empty sequence. There are N operations. The i-th operation contains two integers and . This means that adding integers into the sequence. After each operation, you need to find the median of the sequence.

The first line of the input contains an integer  as described above.

The next two lines each contains six integers in the following format, respectively:

- 
- 

These values are used to generate  as follows:

We define:
- , for 
- , for 


We also define:
- , for .
- , for .

Limits:

You should output lines. Each line contains an integer means the median.

5
3 1 4 1 5 9
2 7 1 8 2 9

3
4
5
4
5

L = [3, 2 ,4, 1, 7]

R = [4, 8, 8, 3, 9]