Cho một mảng gồm \(N\) số đánh số từ \(1 \rightarrow N\). Luân cần viết chương trình thực hiện dãy các lệnh sau:

• "CHANGE i v": Thay đổi số thứ \(i\) thành \(v\)
• "NEGATE a b": Đảo dấu số của tất cả số vị trí từ \(a\) đến \(b\)
• "QUERY a b": Tìm số lớn nhất từ \(a\) đến \(b\)

Dữ liệu vào

• Dòng đầu một số \(N\) \((N \le 10^5)\).
• Dòng tiếp theo chứa \(N\) số \(A_i\)
• Tiếp theo là dãy các lệnh như mô tả ở trên(số lệnh không quá 50000). Cuối mỗi test ghi một từ "DONE".
• Dữ liệu vào luôn đảm bảo trọng số của các cạnh ở mỗi thời điểm có giá trị tuyệt đối không vượt quá \(10^7\)

Dữ liệu ra

• Với mỗi lệnh "QUERY", in ra kết quả tìm được. Nếu \(a=b\) thì ghi ra \(0\).

Input 1

9
1 1 1 4 3 9 7 3 5
CHANGE 6 7
CHANGE 3 6
CHANGE 4 7
CHANGE 5 7
NEGATE 1 5
QUERY 2 4
QUERY 6 8
CHANGE 4 6
QUERY 1 7
QUERY 3 4
DONE

Output 1

-1
7
7
6