Giữa năm 2023, một trường đại học tỉnh nọ tạo điều kiện cho các bạn sinh viên đi chơi trải nghiệm sinh hoạt hè. Đoàn thanh niên bao gồm ~n~ bạn tham gia, bạn thứ ~i~ sẽ có áo lớp mã số màu ~c_i~. Mỗi lớp sẽ gồm những người bạn mặc cùng màu áo và màu áo mỗi lớp là phân biệt. Mọi người đều có tinh thần tham gia để đem về chiến thắng cho cả đội.

Người quản trò sẽ tổ chức trò chơi bao gồm các bạn ~a_l, a_{l+1}, \ldots, a_r~ xếp thành hình tròn. Khi đó:

• Bạn ~a_{i+1}~ được gọi là người tiếp theo với bạn ~a_i~ với mọi ~i = l, l + 1, \ldots, r - 1~.
• Bạn ~a_l~ là người tiếp theo của bạn ~a_r~.

Khi đến lượt chơi của một bạn lớp ~X~, thì người đó có ~2~ lựa chọn:

• Loại đi người tiếp theo, nếu người đó không bạn cùng lớp thì lượt kế tiếp sẽ đi bởi người khác lớp ~X~, ngược lại thì người kế tiếp với người bị loại sẽ đi tiếp. Sau quá trình này vòng tròn sẽ giảm bơt đi một người.
• Bỏ lượt của bản thân, và tới lượt của người tiếp theo.

Các bạn trên vòng tròn sẽ lần lượt thực hiện quá trình trên cho tới khi chỉ còn lại một đội duy nhất. Lớp ~E~ dành được chiến thắng khi bất kể người nào là người bắt đầu, và chiến thuật của các đội có như thế nào, thì vẫn là đội duy nhất còn lại sau quá trình.

Để cho việc trải nghiệm sinh hoạt trở nên phong phú hơn, nhà trường quyết định tổ chức lần lượt ~q~ hoạt động sau:

• Thay đổ màu áo của các bạn ~a_l, a_{l+1}, \ldots, a_r~.
• Tạo một trò chơi gồm các bạn ~a_l, a_{l+1}, \ldots, a_r~.

Input

• Dòng đầu chứa hai số nguyên duy nhất là ~n~ và ~q~ (~1 \leq n, q \leq 2 \cdot 10^4~), số lượng sinh viên tham gia trải nghiệm và số lượng hoạt động nhà trường thực hiện.
• Dòng thứ hai chứa ~n~ số nguyên dương ~c_1, c_2, \ldots, c_n~ (~0 \leq c_i \leq 10^9~), với ~c_i~ nghĩa là mã số màu áo của bạn thứ ~i~ ban đầu đang mặc.
• Sau đó gồm ~q~ dòng miêu tả các hoạt động được thực hiện dần, mô tả một trong hai loại truy vấn như sau:
  • 1 ~l~ ~r~ ~v~: Thay đổ số màu áo của các bạn từ ~a_i~ thành ~a_i + v~ với các bạn ~i = l, l + 1, \ldots r~ (~1 \leq l, r \leq n, |v| \leq 10^9~).
  • 2 ~l~ ~r~: Quản trò tạo một trò chơi gồm các bạn trong đoạn [l, r], in ra màu áo lớp chiến thắng nếu tìm được, ngược lại in ra "IMPOSSIBLE".

Output

• Với mỗi truy vấn loại hai, in ra màu áo đội chiến thắng nếu tìm được, ngược lại in ra IMPOSSIBLE.

Scoring

• Subtask 1 (~40\%~ số điểm): ~n, q \leq 10^3~.
• Subtask 2 (~30\%~ số điểm): ~q \leq 5 \cdot 10^3~, chỉ bao gồm truy vấn loại ~2~.
• Subtask 3 (~30\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input

7 6
1 2 1 2 3 1 1
2 1 7
1 1 3 1
2 2 7
1 4 7 1
2 1 4
2 2 2

Output

1
IMPOSSIBLE
IMPOSSIBLE
3