Mình hợp nhau đến như vậy thế nhưng không phải là yêu
Và em muốn hỏi anh rằng, chúng ta là thế nào?
Rồi lặng người đến vô tận, trách sao được sự tàn nhẫn
Anh trót vô tình, thương em như là em gái

Đừng lo lắng về em khi mà em vẫn còn yêu anh
Càng xa lánh, càng trống vắng, tim cứ đau và nhớ lắm
Đành phải buông hết tất cả thôi
Nụ cười mỉm sau bờ môi
Ấm áp dịu dàng vai anh
Em đã bao lần yên giấc

Nhìn trên cao khoảng trời yêu mà em lỡ dành cho anh
Giờ mây đen quyện thành bão, giông tố đang dần kéo đến
Chồi non háo hức đang đợi mưa
Rất giống em ngày xưa
Mưa trôi để lại ngây thơ trong giấc mơ buốt lạnh
Trích Em Gái Mưa (Hương Tràm)

Khúc ca vẫn còn vang lên và vẫn còn mãi trong lòng những giới trẻ thời 9x thậm chí là đến bây giờ. p2o2HuaGiaBao là một người trẻ sống hòa đồng. Nhưng có những lúc anh ấy gặp khó khắn. Ban đầu, lúc cậu ấy còn là một học sinh cấp \(1\). Anh ta đã có thân thiết với một người bạn khác. Lúc ấy, hai người bạn đó đã không ngừng giúp đỡ nhau từ việc bình thường và nhỏ nhặt nhất cho đến những chuyện học tập, giải trí, ... Ngoài ra, hai người bạn còn thường xuyên trò chuyện, tâm sự, cũng như tặng những món quà tràn đầy ý nghĩa. Mọi chuyện tốt đẹp cho đến khi trongphithien xen vào.
Vì trongphithien đều bị các bạn khác cô lập nên luôn bị FA. Chính vì vậy, anh ấy lên một kế hoạch hoàn hảo là sẽ nói dối với cô bạn thân thiết nhất của cậu ta rằng p2o2HuaGiaBao bắt cá hai tay để có thể dễ dàng làm quen với cô gái này. Ngay khi chuẩn bị thủ đoạn không đẹp của trongphithien thì vô tình bị cô bạn ấy phát hiện và nói với p2o2HuaGiaBao.
Khoảng một tuần sau đó, tin này đã lan ra khắp trường. Lần này không chỉ bạn bè trong lớp hay trường xa lánh mà còn bị sự phê phán của gia đình và thầy cô.
Thi join contest của HGBCpp_ cậu ta bị bí câu này nhưng vì ai ai cũng ghét anh ta hết nên không biết phải nhờ sự trợ giúp ở đâu. Các bạn hãy giúp cậu ấy bài toán dưới đây nhé! Bài toán như sau.
Cho một dãy gồm \(N\) phần tử, phần tử thứ \(i\) có giá trị nguyên \(a_i\). Ta gọi một đoạn con liên tiếp là ổn định nếu tổng các phần tử trên đoạn đó chia hết cho \(3\), đồng thời trong đoạn đó không tồn tại hai phần tử kề nhau cùng mang cùng một giá trị chẵn/lẻ theo thứ tự hiện tại của dãy. Ban đầu dãy được cho trước, sau đó có \(Q\) thao tác online gồm hai loại:

1. Truy vấn cập nhật: 1 x y nghĩa là gán \(a_x=y\)
2. Truy vấn câu hỏi: 2 l r nghĩa là xét đoạn \([l,r]\).
   Với mỗi truy vấn loại 2, hãy tìm giá trị lớn nhất của một đoạn con ổn định nằm hoàn toàn trong \([l,r]\). Nếu không tồn tại đoạn con ổn định nào thì in ra 0.

Input

• Dòng đầu tiên chứa hai số nguyên \(N,Q\). \((1\le N,Q\le 2\cdot10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\dots,a_N\). \((-10^9\le a_i\le 10^9)\)
• \(Q\) dòng tiếp theo, mỗi dòng là một thao tác thuộc một trong hai dạng sau: 1 x y, 2 l r.

Output

• Với mỗi truy vấn loại 2, in ra một số nguyên duy nhất là giá trị lớn nhất tìm được, hoặc 0 nếu không tồn tại đoạn con ổn định.

Example

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

6
3
9
6

5 4
8392 3910 392 4203 1039
1 3 547
1 4 893
2 1 5
2 4 5

0
0