You are given an array of ~n~ integers and must process ~q~ queries of the following types:

1. Change the value at position ~k~ to ~u~.
2. Find the minimum and maximum values over the range ~[l, r]~.

Positions are 1-indexed.

Input

The first line contains the integer ~n~, the size of the array.

The second line contains ~n~ space-separated integers ~x_1, x_2, \ldots, x_n~: the initial values of the array.

The third line contains the integer ~q~, the number of queries.

Each of the next ~q~ lines describes a query and is one of the following:

• 1 k u: set the value at position ~k~ to ~u~
• 2 l r: query the minimum and maximum values over the range ~[l, r]~

Output

For each query of type 2, output a line containing the minimum and maximum of the given range, separated by a space.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le q \le 10^4~
• ~-10^9 \le x_i, u \le 10^9~
• ~1 \le k \le n~
• ~1 \le l \le r \le n~

Example 1

Input

5
-2 0 10 -10 -7 
10
1 4 -2
2 4 5
2 4 5
2 1 3
1 5 6
1 2 -3
1 2 -5
1 5 -5
2 2 3
2 3 5

Output

-7 -2
-7 -2
-2 10
-5 10
-5 10

Example 2

Input

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

Output

-6 -4
-9 10
-3 4
-9 7
-5 7
-9 7
-4 4
-7 6