Cho một mảng ~A~ gồm ~N~ phần tử và ~Q~ truy vấn. Mỗi truy vấn cho ~4~ tham số ~l,r,v,k~. Với mỗi truy vấn ta phải làm thao tác sau: $$\forall i\in [l,r] :a_i=(a_i+v*k^{i-l} )\%(10^9+7)$$ Hãy in ra mảng ~A~ sau ~Q~ truy vấn.

Input

• Dòng đầu gồm ~2~ số nguyên ~N,Q(1\le N,Q\le2*10^5)~

• ~Q~ dòng tiếp theo, mỗi dòng gồm ~4~ số ~l,r,v,k(1\le l\le r\le n,1\le v\le 10^9,1\le k\le 200)~

Output

• Gồm ~N~ số là giá trị của mảng ~A~ sau ~Q~ truy vấn.

Sample Input 1

5 3
2 3 7 7
3 5 2 13
1 5 6 9

Sample Output 1

6 61 537 4400 39704

Notes

Sau truy vấn thứ nhất, các phần tử trong dãy ~A~ lần lượt bằng ~0,7,49,0,0~.

Sau truy vấn thứ hai, các phần tử trong dãy ~A~ lần lượt bằng ~0,7,51,26,338~.

Sau truy vấn thứ ba, các phần tử trong dãy ~A~ lần lượt bằng ~6,61,537,4400,39704~.