Lại là thực hiện truy vấn!

Lần này, bạn được cho một mảng \(a\) có \(n\) phần tử. Ban đầu, tất cả các phần tử trong mảng \(a\) có giá trị bằng \(0\). Bạn phải thực hiện \(Q\) truy vấn, mỗi truy vấn thuộc một trong hai dạng:

• 1 l r x: Tăng toàn bộ các phần tử trong mảng \(a\) từ vị trí \(l\) đến vị trí \(r\) một giá trị bằng \(x\).
• 2 l r x: Giảm toàn bộ các phần tử trong mảng \(a\) từ vị trí \(l\) đến vị trí \(r\) một giá trị bằng \(x\).

Yêu cầu: In ra dãy \(a\) sau \(Q\) truy vấn?

Input

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

Output

• Một dòng chứa \(n\) số nguyên là dãy \(a\) sau truy vấn. Lưu ý nếu có tồn tại các số \(0\) đằng sau cũng cần in đủ.

Scoring

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

Example

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

1 2 1 -1 -1