Min Max Dynamic Queries

Given an array of ~n~ integers, process the following ~q~ queries of the following types:

1. Change the ~k~-th value to ~u~.
2. What is the min and max value over the range ~[l,r]~. (1-Indexed)

Input

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

The second line has ~n~ space seperated integers ~x_1, x_2,\dots,x_n~: the values within the array.

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

The following ~q~ lines describe the queries. Each line contains either "~1~ ~k~ ~u~", updating the ~k~-th value to ~u~, or "~2~ ~l~ ~r~" querying the min and max value over ~[l,r]~.

Output

For each query of type 2, output a line containing the min and max of the given interval, seperated by a space.

Contraints

• ~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