Giá trị lớn nhất ver2 ( QMAX2 )

Giới hạn
  • Thời gian: 0.421s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

 

Giống bài "Giá trị lớn nhất" ở trên.

Input

  • n: số phần tử của dãy (n <= 50000).
  • m: số lượng biến đổi và câu hỏi (m <= 100000).
    • biến đổi có dạng: 0 x y value
    • câu hỏi có dạng : 1 x y.

Output

Ghi ra trả lời cho lần lượt từng câu hỏi.

Example

Input:
6 3
0 1 3 3
0 4 6 4
1 1 6

Output:
4


  • Người up: dtmp
  • Điểm: 0.07
  • Ngôn ngữ cho phép: