Hải được Thầy giáo cho dãy ~a~ gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~. Ban đầu, ~a_1 = a_2 = \dots = a_n = 1~. Hải thực hiện ~q~ thao tác dạng ~[L, R, k, x]~, mỗi thao tác nhân các phần tử ở các vị trí ~L + t \times k~ (với ~0 \le t \le \lfloor \frac{R-L}{k} \rfloor~) lên ~x~ lần.

Hãy in ra dãy ~a~ sau khi thực hiện đủ ~q~ thao tác. Vì các giá trị ~a_i~ (~1 \le i \le n~) có thể rất lớn nên chỉ cần tính theo phần dư của phép chia ~a_i~ cho ~10^9 + 7~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, q~ (~1 \le n \le 5 \times 10^4, 1 \le q \le 2 \times 10^5~) lần lượt là độ dài dãy ~a~ và số lượng thao tác;
• ~q~ dòng sau, mỗi dòng gồm bốn số nguyên dương ~L, R, k, x~ (~1 \le L \le R \le n, 1 \le k \le n, 1 \le x \le 10^9~) mô tả một thao tác. Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

• Ghi ra trên một dòng gồm ~n~ số nguyên dương là dãy ~a~ sau ~q~ thao tác, các số cách nhau bởi dấu cách.

Sample Input 1

5 2
1 4 2 4
1 5 2 3

Sample Output 1

12 1 12 1 3