Tấn là một người theo chủ nghĩa không hoàn hảo. Anh rất ghét những thứ hoàn hảo, số hoàn hảo cũng không phải ngoại lệ.

Một số \(x\) nguyên dương được gọi là số hoàn hảo, khi:

Trọng đó, \(s(x)\) là hàm tổng các ước của \(x\), không bao gồm \(x\).

Một hôm, anh gặp bài tập về dãy số như sau:

Xét dãy \(a\) gồm \(n\) số nguyên, ban đầu đều là \(0\), thực hiện \(q\) truy vấn thuộc \(2\) loại sau trên dãy \(a\):

• \(1\) \(l\) \(r\) \(v\) : \(a_i = v (1 \le l \le i \le r \le n, 0 \le v \le 10^9)\).
• \(2\) \(l\) \(r\) \(v\) : \(a_i = a_i + v (1 \le l \le i \le r \le n, 0 \le v \le 10^9)\).

Sau khi thực hiện \(q\) truy vấn thì in ra mảng \(a\).

Tuy nhiên có một vấn đề : Vì Tấn không thích số hoàn hảo, nên dãy \(a\) không được có sự xuất hiện của số hoàn hảo. Vậy nên khi thực hiện truy vấn \(i\), nếu trong dãy có số hoàn hảo xuất hiện, thực hiện tăng các số có vị trí từ \(l_i . . . r_i\) của dãy \(a\) lên \(1\) liên tục cho đến khi dãy không còn số hoàn hảo nào.

Tuy nhiên việc này vô tình khiến bài toán trở nên khó hơn rất nhiều. Hơn nữa Tấn đang cần học bài để thi kiểm tra trên lớp. Các bạn hãy giúp Tấn giải bài toán nhé.

Input

• Dòng đầu nhập 2 số \(n\) và \(q\) lần lượt là số phần tử của dãy \(a\) và số truy vấn. \((1 \le n, q \le 10^5)\).
• \(q\) dòng tiếp theo, mỗi dòng nhập vào \(4\) số nguyên dương \(type\) \(l\) \(r\) \(v\) \((1 \le type \le 2)\).

Output

• In ra mảng sau khi thực hiện \(q\) truy vấn.

Scoring

• Subtask \(1\) (40% số điểm): \(n, q \le 10^3\)
• Subtask \(2\) (60% số điểm): Không có ràng buộc gì thêm

Example

5 7
2 1 5 1 
2 2 5 1 
2 3 5 1 
2 4 5 1 
2 5 5 1 
2 3 5 1 
1 1 3 28 

29 29 29 8 9