Hạo là một kỹ sư phần mềm làm việc tại một công ty phát triển game chiến lược. Trong một nhiệm vụ đặc biệt, Hạo được giao quản lý sức mạnh của một nhóm nhân vật trong trò chơi. Mỗi nhân vật trong nhóm có chỉ số sức mạnh ban đầu khác nhau, và chỉ số này có thể thay đổi dựa trên những sự kiện trong trò chơi. Có hai loại sự kiện mà Hạo cần xử lý:

Sự kiện tăng sức mạnh: Một số nhân vật trong nhóm sẽ được tăng sức mạnh sau khi hoàn thành nhiệm vụ hoặc chiến đấu thành công.

Sự kiện kiểm tra sức mạnh đặc biệt: Hạo cần đếm xem có bao nhiêu nhân vật trong nhóm hiện tại có sức mạnh là bội số của \(3\), vì những nhân vật này có khả năng kích hoạt những kỹ năng đặc biệt khi sức mạnh của họ chia hết cho \(3\). Nhóm của Hạo gồm \(n\) nhân vật, mỗi nhân vật có một chỉ số sức mạnh ban đầu và trong quá trình diễn ra trò chơi, Hạo sẽ nhận được nhiều yêu cầu về việc thay đổi sức mạnh hoặc kiểm tra sức mạnh đặc biệt của một nhóm nhân vật.

Bài toán: Cho mảng số nguyên \(A\) gồm \(n\) phần tử, mỗi phần tử đại diện cho chỉ số sức mạnh của một nhân vật trong nhóm. Hạo sẽ nhận được \(q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• \(1\) \(l\) \(r\): Tăng sức mạnh của tất cả các nhân vật từ vị trí \(l\) đến \(r\) trong mảng thêm \(1\) đơn vị.
• \(2\) \(l\) \(r\): Kiểm tra có bao nhiêu nhân vật trong nhóm từ vị trí \(l\) đến \(r\) hiện tại có chỉ số sức mạnh là bội số của \(3\).

Input 1

• Dòng đầu tiên gồm \(2\) số nguyên \(n,q\)
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\)
• \(q\) dòng tiếp theo, mỗi theo gồm \(3\) số nguyên, một truy vấn.

Output 1

• In ra đáp án cho mỗi truy vấn loại \(2\).

Điều kiện

• \(1 \le n, q \le 10^5\)
• \(1 \le l, r \le n\)
• \(1 \le A_i \le 10^9\)

Input 1

5 3
1 2 2 3 2
2 2 4
1 1 5
2 3 5

Output 1

1
2

Input 2

7 5
6 9 10 7 9 1 3
1 5 5
2 2 4
2 4 5
2 2 4
1 3 3

Output 2

1
0
1