Hảo Hảo, cảm nhận từng giây hạnh phúc

Bạn là chủ một hệ thống nhà hàng chuyên bán mì ăn liền. Tại sao lại là mì ăn liền, đó là vì "dẫu thời gian mang đến nhiều đổi thay, những điều tuyệt vời vẫn còn đó trên mảnh đất này. Hảo Hảo, cảm nhận từng giây hạnh phúc".

Khi xem các quảng cáo mì ăn liền, ta đều thấy cả nhà cùng ngồi ăn mì và cười hạnh phúc, hay là người mẹ đi làm và mua mì về thì cả nhà cùng nhau reo hò. Mì thường được làm từ "trứng vàng" (~\le~15g/1kg) hay khoai tây (~\approx~20g/1kg) rất tốt cho sức khỏe, trong khi đó thành phần sắn thì chỉ là thành phần phụ (~\approx~900g/1kg). Nhà hàng của bạn có n gói mì đủ loại, mỗi gói có độ ngon là ~a_i~ (~|a_i|\le10^9~). Bạn cần xử lý 2 loại truy vấn như sau:

• Loại 1 có dạng ~1~ ~x~ ~y~: Nấu gói mì ở vị trí thứ ~x~ và mua gói mì có độ ngon ~y~ thay vào đó. (~1\le x \le n,|y|\le10^9~)
• Loại 2 có dạng ~2~ ~l~ ~r~: In ra độ ngon lớn nhất của các gói mì từ vị trí ~l~ đến ~r~ (~1\le l\le r\le n~)

Với mỗi truy vấn loại 2, hãy in ra câu trả lời trên một dòng.

Input

• Dòng đầu tiên là số ~n~ là số các gói mì (~1\le n\le10^5~)
• Dòng 2 là ~n~ số nguyên là độ ngon của các gói mì (~|a_i|\le10^9~)
• Dòng 3 là 1 số ~q~ là số truy vấn(~1\le q \le10^5~)
• ~q~ dòng sau, mỗi dòng là một truy vấn thuộc một trong hai loại trên.

Output

Với mỗi truy vấn loại 2, in ra câu trả lời trên một dòng

Sample Input

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

Sample Output

4
5
5
3