Sau khi tốt ngành thời gian học, Kuroni bắt đầu khởi nghiệp và thành lập công ty quản lý thời gian OURO. Sau 1000 năm hoạt động, từ một công ty nhỏ lẻ, OURO đã trở thành công ty quy mô đa vũ trụ. Vừa qua, công ty đã phát hành thêm một loại cổ phiếu mới với lợi nhuận được dự báo sẽ bay lên thẳng mặt trăng.

Có ~n~ cổ đông muốn đầu tư vào loại cổ phiếu này. Các cổ đông được đánh số từ ~1~ đến ~n~. Ban đầu, các cổ đông đều không có cổ phiếu, và tài khoản của họ đều có số tiền bằng ~0~. Có ~q~ sự kiện sẽ diễn ra, các sự kiện thuộc một trong các loại sau:

• ~\texttt{1} \; p \; x~ — Cổ đông ~p~ mua vào ~x~ cổ phiểu (nếu ~x \ge 0~), hoặc bán đi ~|x|~ cổ phiếu (nếu ~x < 0~);

• ~\texttt{2} \; v~ — Công ty kinh doanh có lãi, thu về cổ tức ~v~. Mọi cổ đông đang sở hữu cổ phiếu đều thu về số tiền tỉ lệ với số cổ phiếu. Cụ thể, gọi ~s~ là số cổ phiếu mà một cổ đông sở hữu thì số tiền mà tài khoản của cổ đông đó nhận được sẽ tăng thêm ~s \cdot v~.

• ~\texttt{3} \; p~ — Cổ đông ~p~ sẽ tiến hành rút toàn bộ số tiền hiện có trong tài khoản. Sau khi rút thì số tiền trong tài khoản của cổ đông ~p~ sẽ trở về ~0~.

Với mỗi sự kiện loại ~3~, hãy cho biết số tiền mà cổ đông sẽ thu về được. Vì đáp án có thể rất lớn, bạn có thể in đáp án sau khi chia lấy phần dư cho ~10^9 + 7~.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 5 \cdot 10^5~) — số cổ đông và số sự kiện.

Dòng thứ ~i~ trong ~q~ dòng tiếp theo mô tả sự kiện thứ ~i~ với định dạng như mô tả trong đề bài.

• ~\texttt{1} \; p \; x~ (~1 \le p \le n~, ~-10^9 \le x \le 10^9~) — mô tả sự kiện loại 1. Đảm bảo rằng sau mỗi sự kiện này, không có cổ đông nào có số cổ phiếu âm.

• ~\texttt{2} \; v~ (~1 \le v \le 10^9~) — mô tả sự kiện loại 2.

• ~\texttt{3} \; p~ (~1 \le p \le n~) — mô tả sự kiện loại 3.

Output

Với mỗi sự kiện loại ~3~, in ra số tiền mà cổ đông thu về được sau khi chia lấy phần dư cho ~10^9 + 7~.

Scoring

Tổng điểm cho bài này là ~1500~.

Sample Input 1

3 8
1 1 5
2 3
1 2 10
2 2
3 1
2 4
3 2
3 1

Sample Output 1

25
60
20

Sample Input 2

1 8
1 1 1000
2 1
1 1 -100
2 2
3 1
1 1 -200
2 3
3 1

Sample Output 2

2800
2100

Notes

Trong ví dụ đầu tiên có ~n = 3~ cổ đông. Chỉ có cổ đông ~1~ và ~2~ thực hiện đầu tư.

Bảng dưới đây mô tả các sự kiện có liên quan đến cổ đông ~1~.

Bảng dưới đây mô tả các sự kiện có liên quan đến cổ đông ~2~.

Trong ví dụ thứ hai, có ~n = 1~ cổ đông. Bảng dưới đây mô tả các sự kiện của ví dụ thứ hai.