Tại thành phố nọ, có ~n~ cột đá, cột đá thứ ~i~ có chỉ số kỹ năng ~a_i~. Bạn được giao nhiệm vụ xử lý ~q~ truy vấn thuộc hai loại sau đây:

• Loại 1: ~1\ l\ v~

  • Đây là truy vấn cập nhật;

  • Chỉ số kỹ năng của cột đá thứ ~l~ được thay đổi thành ~v~;

• Loại 2: ~2\ l\ r\ k~

  • Đây là truy vấn báo cáo;

  • Yêu cầu tìm giá trị kỹ năng nhỏ thứ ~k~ trong đoạn các cột đá từ ~l~ đến ~r~ (tính cả ~l~ và ~r~).

Input

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 10^5)~;

• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9; i=1,2,\dots,n)~ - chỉ số kỹ năng ban đầu;

• Dòng tiếp theo chứa một số nguyên dương ~q~ ~(1 \le n \le 10^5)~;

• ~q~ dòng tiếp theo, mỗi dòng chứa một truy vấn thuộc một trong hai loại:

  • ~1\ l\ v~ ~(1 \le l \le n, 1 \le v \le 10^9)~;

  • ~2\ l\ r\ k~ ~(1 \le l \le r \le n; 1 \le k \le r-l+1)~.

Output

Với mỗi truy vấn Loại 2, in ra kết quả là một số nguyên duy nhất trên một dòng.

Scoring

Sample Input 1

5
1 2 3 4 5
3
2 2 4 2
1 3 6
2 2 4 2

Sample Output 1

3
4