#845. NOST - Không segment tree

Thầy giáo có điểm của học sinh: . Học sinh thứ có điểm là . Thầy giáo giao cho bạn hai loại câu hỏi như sau:

• Loại : dạng là yêu cầu bạn cập nhật lại bạn thứ với điểm số là ;
• Loại : dạng là hỏi giữa đoạn thì hai điểm bằng nhau nào có khoảng cách xa nhất, nếu không có hai điểm bằng nhau thì in ra điểm nhỏ nhất trên đoạn đó, nếu có khoảng cách bằng nhau thì in ra điểm nhỏ nhất trong số những cặp có khoảng cách xa nhất đó.

Dữ liệu vào:

• Dòng đầu chứa hai số là số học sinh và số câu hỏi ;
• Dòng tiếp theo là điểm ban đầu của học sinh;
• dòng tiếp theo cho tương ứng câu hỏi theo định dạng như trên.

Dữ liệu ra:

• Với mỗi câu hỏi loại thì in ra một số là kết quả tương ứng.

Ví dụ:

Dữ liệu vào:

5 6
12 13 13 12 1
2 1 3
2 1 2
2 1 5
1 3 5
1 1 5
2 1 3

Dữ liệu ra:

13
12
12
5

Giải thích:

Có bạn học sinh, câu hỏi:

• Câu trong đoạn in ra vì khoảng cách lớn nhất là ;
• Câu trong đoạn không có điểm nào lặp lại;
• Câu 12$ vì có khoảng cách xa nhất;
• Sau 2 câu cập nhật thì câu cuối cùng in ra .