Bạn được cho một mảng \(a\) có \(n\) phần tử. Bạn phải xử lí \(Q\) truy vấn, mỗi truy vấn thuộc một trong hai dạng:

• 1 x: Tăng tất cả các phần tử trong mảng đang có giá trị chẵn \(x\) đơn vị.
• 2 x: Tăng tất cả các phần tử trong mảng đang có giá trị lẻ \(x\) đơn vị.

Chú ý rằng, trong các truy vấn, chúng ta xét giá trị của \(a_{i}\), chứ không xét chỉ số.

Yêu cầu: Đưa ra tổng của mảng \(a\) sau mỗi truy vấn?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n, Q\) (\(n, Q \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1}, a_{2},..., a_{n}\) (\(a_{i} \le 10^6\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn như mô tả ở trên (\(1 \le x \le 10^4\)).

Output

• Đưa ra \(Q\) số nguyên trên \(Q\) dòng, dòng thứ \(i\) chứa một số nguyên duy nhất là tổng của mảng sau khi thực hiện truy vấn thứ \(i\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(Q \le 10\).
• Subtask \(2\) (\(70\%\) số điểm): không có ràng buộc gì thêm.

1 2
2 
1 1
2 1

3
4