Alice có $n$ chiếc đèn, mỗi chiếc đèn có 3 màu: đỏ, vàng hoặc xanh. Ban đầu, các đèn đang có các màu lần lượt là $a_1,a_2,...,a_n$, với $a_i=0$ nếu đèn thư $i$ có màu xanh, $a_i=1$ nếu đèn thứ $i$ có màu vàng, $a_i=2$ nếu đèn thứ $i$ có màu đỏ. Các đèn được nối với nhau thành một dãy. Có $n$ nút bấm, nút bấm thứ $i$ chuyển đổi trạng thái các đèn có vị trí từ $1$ đến $i$: đèn xanh chuyển sang đèn vàng, đèn vàng chuyển sang đèn đỏ, đèn đỏ chuyển sang đèn xanh.

Alice muốn biết cô ta cần phải ấn các nút bấm bao nhiêu lần để toàn bộ dãy đèn trở thành màu xanh. Tuy nhiên cô nhận thấy bài toán này vẫn còn quá dễ nên cô muốn biến nó thành một bài toán khó hơn. Cụ thể, Alice sẽ thực hiện thay đổi trạng thái các đèn $q$ lần. Mỗi lần, Alice sẽ chọn ra ba số nguyên dương $l,r,k$. Alice sẽ thực hiện thay đổi trạng thái đèn thứ $l$ $1^k$ lần, đèn thứ $l+1$ $2^k$ lần, ..., đèn thứ $r$ $(r-l+1{)}^k$ lần. Sau mỗi lần thay đổi, Alice muốn biết cô ta cần phải ấn nút tối thiểu bao nhiêu lần để toàn bộ dãy đèn trở thành màu xanh.

Dữ liệu

• Dòng đầu tiên gồm hai số nguyên dương $n,q$ $(1\le n,q\le {10}^5)$.
• Dòng tiếp theo gồm $n$ số nguyên dương $a_1,a_2,...,a_n$ $(0\le a_i\le 2)$.
• $q$ dòng tiếp theo, mỗi dòng gồm ba số nguyên dương $l,r,k$ $(1\le l\le r\le n,0\le k\le {10}^9)$.

Kết quả

Gồm $q+1$ dòng:

• Dòng đầu tiên gồm một số nguyên dương là số lần ấn nút tối thiẻu đẻ toàn bộ dãy đèn trở thành màu xanh trong trạng thái đèn đầu tiên.
• $q$ dòng tiếp theo, dòng thứ $i$ gồm một số nguyên dương là số lần ấn nút tối thiẻu đẻ toàn bộ dãy đèn trở thành màu xanh trong trạng thái đèn sau lần thay đổi thứ $i$.

Ví dụ

Dữ liệu

5 2
0 1 1 2 2
4 5 1
1 1 2

Kết quả

3
6
5

Giải thích

• Trong trạng thái đèn đầu tiên, cần ấn các nút $1,3,5$ mỗi nút một lần để các đèn được biến đổi: $(0,1,1,2,2)\to$ $(1,1,1,2,2)\to$ $(2,2,2,2,2)$ $\to (0,0,0,0,0)$.
• Sau lần thay đổi đầu tiên, dãy đèn trở thành $(0,1,1,0,1)$. Cần ấn nút $1$ 1 lần, nút $3$ 2 lần, nút $4$ 1 lần, nút $5$ 2 lần.
• Sau lần thay đổi thứ hai, dãy đèn trở thành $(1,1,1,0,1)$. Ấn các nút tương tự như trên, trừ nút $1$.