Simple

Time limit1sMemory limit512 MB

Summary

Support range add updates and range queries for the minimum even and maximum odd value, printing -1 for a missing parity.

Level: Hard8 of 10
Topics: Segment tree, Linked list, Implementation, Math
Solved: No attempts yet

Problem

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

0 a b val : add val to every number in the interval [a,b]
1 a b : print the minimum even number and the maximum odd number in the interval [a,b]. If one of these numbers does not exist, print -1 in its place.

Answer all type 1 queries.

Input

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

Output

Print the answers to all type 1 queries, one per line.

Constraints

The numbers in the sequence are between 1 and 2,000,000,000.
The value val in a type 0 query is between 1 and 2,000,000,000.
WARNING!! If one of the answers to a type 1 query cannot be computed, print -1 in its place!!

Examples1

Example 1

Input

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

Expected output