After completing his studies, Kuroni started a business and founded the time management company OURO. After 1000 years of operation, OURO has grown from a small company to a multi-universe scale enterprise. Recently, the company has released a new type of stock with profits forecasted to soar straight to the moon.

There are ~n~ shareholders who want to invest in this stock. The shareholders are numbered from ~1~ to ~n~. Initially, all shareholders have no stocks, and their accounts have a balance of ~0~. There will be ~q~ events that occur, which belong to one of the following types:

• ~\texttt{1} \; p \; x~ — Shareholder ~p~ buys ~x~ shares (if ~x \ge 0~), or sells ~|x|~ shares (if ~x < 0~);

• ~\texttt{2} \; v~ — The company is profitable and receives dividends of ~v~. Every shareholder who owns shares will receive an amount proportional to the number of shares they hold. Specifically, let ~s~ be the number of shares a shareholder owns, then the amount credited to that shareholder's account will increase by ~s \cdot v~.

• ~\texttt{3} \; p~ — Shareholder ~p~ will withdraw the entire amount currently in their account. After the withdrawal, the balance in shareholder ~p~'s account will return to ~0~.

For each event of type ~3~, please report the amount that the shareholder will receive. Since the answers can be very large, you may print the answer after taking the modulus with ~10^9 + 7~.

Input

The first line contains two integers ~n~ and ~q~ (~1 \le n, q \le 5 \cdot 10^5~) — the number of shareholders and the number of events.

The ~i~-th line in the following ~q~ lines describes the ~i~-th event in the format as described in the problem statement.

• ~\texttt{1} \; p \; x~ (~1 \le p \le n~, ~-10^9 \le x \le 10^9~) — describes an event of type 1. It is guaranteed that after each of these events, no shareholder will have a negative number of shares.

• ~\texttt{2} \; v~ (~1 \le v \le 10^9~) — describes an event of type 2.

• ~\texttt{3} \; p~ (~1 \le p \le n~) — describes an event of type 3.

Output

For each event of type ~3~, print the amount that the shareholder receives, modulo ~10^9 + 7~.

Scoring

The total score for this problem is ~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

In the first example, there are ~n = 3~ shareholders. Only shareholders ~1~ and ~2~ make investments.

The table below describes the events related to shareholder ~1~.

The table below describes the events related to shareholder ~2~.

In the second example, there is ~n = 1~ shareholder. The table below describes the events of the second example.