simple

You are given a sequence of $N$ numbers and $Q$ queries:

• 0 a b val: the number $val$ will be added to all of the numbers from the interval $[a,b]$
• 1 a b: you need to print the minimum even number and the maximum odd number from the interval $[a,b]$; if one of these numbers does not exist, $-1$ will be printed in its place

Task

Answer all of the type 1 queries.

Input data

The first line contains one integer $N$. The second line contains $N$ integers, representing the numbers from the sequence. The third line contains one integer $Q$, and the following $Q$ lines contain $Q$ queries, as described in the statement.

Output data

The output contains the answers to all of the type 1 queries, one per line.

Constraints and clarifications

• $N, Q \leq 200 \ 000$
• The numbers from the sequence are between $1$ and $2 \ 000 \ 000 \ 000$.
• The numbers $val$ from type 0 queries are between $1$ and $2 \ 000 \ 000 \ 000$.
• WARNING! If one of the answers to a type 1 query cannot be calculated, $-1$ will be printed in its place!

Example

stdin

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

stdout

6 9
8 5
4 11
4 11
4 13
-1 11
4 -1

Explanation

The initial sequence is: $5 \ 6 \ 3 \ 1 \ 9 \ 8 \ 5$.

Query 1 2 5: You will print the specified two numbers from the interval $[2, 5]$.

Query 0 2 3 2: The new sequence is $5 \ 8 \ 5 \ 1 \ 9 \ 8 \ 5$.

Query 1 2 4: You will print the specified two numbers from the interval $[2, 4]$.

Query 0 2 7 3: The new sequence is $5 \ 11 \ 8 \ 4 \ 12 \ 11 \ 8$.

Query 1 2 4: You will print the specified two numbers from the interval $[2, 4]$.

Query 1 4 7: You will print the specified two numbers from the interval $[4, 7]$.

Query 0 5 7 1: The new sequence is $5 \ 11 \ 8 \ 4 \ 13 \ 11 \ 8$.

Query 1 1 6: You will print the specified two numbers from the interval $[1, 6]$.

Query 1 1 2: You will print the specified two numbers from the interval $[1, 2]$.

Query 1 3 4: You will print the specified two numbers from the interval $[3, 4]$.