Cho một danh sách các cặp số nguyên là "cặp số thân thiện", quan hệ cặp số thân thiện là một chiều, tức nếu ~(x,y)~ là cặp số thân thiện thì ~(y,x)~ chưa chắc là cặp số thân thiện. Đồng thời, một số có thể không thân thiện với chính nó.

Một dãy số nguyên ~a_1,a_2,\dots,a_n~ được gọi là "dãy số thân thiện" nếu tất cả các cặp số nguyên ~(a_i,a_{i+1})~ là cặp số thân thiện ~(1 \le i \le n-1)~.

Cho dãy số nguyên ~a_1,a_2,\dots,a_n~ cần trả lời câu hỏi sau: Nếu được phép thay mỗi số nguyên ~a_i \le 0~ ~(1 \le i \le n)~ của dãy số này bởi một số nguyên dương (giữ nguyên các phần tử còn lại), để thu được một "dãy số thân thiện" có tổng giá trị các phần tử lớn nhất là bao nhiêu?

Để tăng độ khó cho bài toán, bạn cần thực hiện ~q~ thao tác biến đổi trên dãy ~a~. Mỗi thao tác biến đổi được mô tả bởi bốn tham số ~l,r,x,y~ với ý nghĩa như sau:

~a[j]=(x+(j-l) \cdot y) \bmod 4~ với mọi ~l \le j \le r~ (~\bmod~ là phép toán chia lấy số dư).

Yêu cầu: Cho dãy số nguyên ~a_1,a_2,\dots,a_n~ và các thao tác biến đổi. Hãy đưa ra đáp án cho câu hỏi trên với dãy số ở thời điểm ban đầu và sau mỗi thao tác biến đổi.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n,q \le 10^5)~;

• Trong ba dòng tiếp theo, mỗi dòng chứa ba số nguyên, mỗi số nguyên là ~0~ hoặc ~1~. Số thứ ~j~ của hàng thứ ~i~ là ~1~ nếu ~(i,j)~ là cặp số thân thiện, là ~0~ nếu ngược lại;

• Dòng tiếp theo chứa ~n~ số nguyên ~a_1,a_2,\dots,a_n~ ~(0 \le a_i \le 3)~ thể hiện dãy số ở thời điểm ban đầu;

• Trong ~q~ dòng cuối cùng, mỗi dòng chứa bốn số nguyên ~l,r,x,y~ ~(1 \le l \le r \le n, 0 \le x,y \le 3)~ mô tả một thao tác biến đổi.

Output

Gồm ~q+1~ dòng, mỗi dòng ghi một số nguyên là kết quả tính được tương ứng với dãy số ở thời điểm ban đầu và kết quả sau mỗi thao tác biến đổi. Kết quả là giá trị lớn nhất của tổng các phần tử trong một "dãy số thân thiện" thu được, hoặc ~-1~ nếu không thể tạo được một "dãy số thân thiện".

Scoring

Sample Input 1

4 2
1 1 0
1 1 1
1 0 0
0 1 0 2
1 4 2 3
1 2 3 0

Sample Output 1

8
8
-1

Notes

Trong ví dụ trên, có ~6~ cặp số thân thiện là ~(1,1)~, ~(1,2)~, ~(2,1)~, ~(2,2)~, ~(2,3)~ và ~(3,1)~.

Ở thời điểm đầu tiên, dãy số là ~(0,1,0,2)~. Từ dãy số này, ta có ~6~ cách thay các số ~0~ để thu được một "dãy số thân thiện":

~(1,1,1,2)~, ~(1,1,2,2)~, ~(2,1,1,2)~, ~(2,1,2,2)~, ~(3,1,1,2)~ và ~(3,1,2,2)~. Giá trị lớn nhất của tổng các số trong dãy là ~3+1+2+2=8~.

Sau thao tác thứ nhất, dãy số trở thành ~(2,1,0,3)~. Từ dãy số này, cách duy nhất để thu được một "dãy số thân thiện" là ~(2,1,2,3)~ với tổng các số trong dãy là ~2+1+2+3=8~.

Sau thao tác thứ hai, dãy số trở thành ~(3,3,0,3)~. Do ~(3,3)~ không phải là cặp số thân thiện, ta không có cách nào để thu được một "dãy số thân thiện".