Cho một mảng ~A~ gồm ~N~ phần tử ~a_1, a_2, \ldots, a_N~. Có ~Q~ truy vấn cần thực hiện, mỗi truy vấn thuộc một trong hai loại sau:

• Truy vấn loại 1: Cú pháp ~1\ l\ x~, nhân tất cả các phần tử từ vị trí ~l~ đến ~N~ (tức là ~a_i~ với ~l \le i \le N~) với số nguyên ~x~.
• Truy vấn loại 2: Cú pháp ~2\ p\ y~, cộng thêm số nguyên ~y~ vào phần tử ~a_p~.

Yêu cầu

Sau khi thực hiện tất cả ~Q~ truy vấn, hãy in ra giá trị của các phần tử trong mảng ~A~. Do kết quả có thể rất lớn, hãy in ra phần dư của mỗi phần tử khi chia cho ~10^9 + 7~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ là các phần tử ban đầu của mảng ~A~.
• ~Q~ dòng tiếp theo, mỗi dòng mô tả một truy vấn có dạng ~1\ l\ x~ hoặc ~2\ p\ y~.

Output

In ra ~N~ số nguyên trên một dòng, cách nhau bởi khoảng trắng, là giá trị của các phần tử ~a_1, a_2, \ldots, a_N~ sau khi thực hiện các phép tính và chia lấy dư cho ~10^9 + 7~.

Ràng buộc

• ~1 \le N, Q \le 10^6~
• ~|a_i| \le 10^9~
• ~1 \le l, p \le N~
• ~|x|, |y| \le 10^9~

Subtasks

• Subtask 1 (30%): ~N, Q \le 5000~
• Subtask 2 (30%): Các truy vấn loại ~1~ luôn có ~l = 1~
• Subtask 3 (20%): ~N, Q \le 10^5~
• Subtask 4 (20%): Không có ràng buộc gì thêm.

Ví dụ

Input

5 4
1 2 3 4 5
2 3 10
1 2 2
2 5 -3
1 4 3

Output

1 4 26 24 21

Giải thích

Ban đầu: ~[1, 2, 3, 4, 5]~

• Sau truy vấn ~2\ 3\ 10~: ~[1, 2, 13, 4, 5]~
• Sau truy vấn ~1\ 2\ 2~: ~[1, 4, 26, 8, 10]~
• Sau truy vấn ~2\ 5\ (-3)~: ~[1, 4, 26, 8, 7]~
• Sau truy vấn ~1\ 4\ 3~: ~[1, 4, 26, 24, 21]~

```