Min Max Queries

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

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

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

Example 2

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

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