Background

A programming website BTC has been placing technology template problems as the last question in its Beginner Contest. In anger, APJifengc poured several bottles of iced black tea on its judging machines, causing some judging units to run $10^{12}$ times faster, making brute force solutions as fast as correct solutions.

Since BTC can no longer use technology template problems, the site administrator wants you to maintain the number of available judging units after each instance of APJifengc pouring iced black tea, in order to coordinate judging resources and post-disaster reconstruction.

Hack data has been added, located in Subtask 5, and is not scored.

Problem Description

There are $n$ bots lined up in a row, and every day all bots drink iced black tea.

You need to dynamically maintain a row of bots with three types of operations or queries:
- 1 l r k, indicating that bots in the range $[l, r]$ will drink $k$ bottles of original flavor iced black tea, and bots outside $[l, r]$ will drink $k$ bottles of tropical flavor iced black tea.
- 2 l r k, indicating that the BTC site administrator angrily destroys the bots in $[l, r]$ that have consecutively drunk at least $k$ bottles of the same flavor of iced black tea.
- 3, querying the number of surviving bots.

Note: In operation 2, the destruction does not change the numbering of the bots.

Input Format

The first line contains two positive integers $n, q$.

The next $q$ lines, each describing an operation or query, are in one of the following three formats:
- 1 l r k;
- 2 l r k;
- 3.

Output Format

Several lines, each answering a query of type 3.

Sample Input and Output

Input Sample #1

5 12
1 3 4 8
3
2 3 4 6
3
1 2 2 3
3
2 1 5 6
3
1 2 3 3
3
2 1 5 3
3

Output Sample #1

5
3
3
1
1
0

Input Sample #2

9 18
1 8 9 5
3
1 5 8 20
3
2 8 9 18
3
2 6 9 6
3
2 1 2 5
3
2 9 9 8
3
2 3 9 14
3
1 6 8 13
3
2 3 5 17
3

Output Sample #2

9
9
7
5
3
3
0
0
0

Notes

Sample 1 Explanation

Only explaining operations 1 and 2.

In the first operation, bots 3 and 4 drink 8 bottles of original flavor iced black tea, and other bots drink 8 bottles of tropical flavor iced black tea.

In the second operation, bots 3 and 4 have consecutively drunk 8 bottles of original flavor iced black tea and are destroyed, leaving 3 surviving bots.

In the third operation, bot 2 drinks 3 bottles of original flavor iced black tea, and other bots drink 3 bottles of tropical flavor iced black tea.

In the fourth operation, bots 1 and 5 have consecutively drunk 11 bottles of tropical flavor iced black tea and are destroyed, leaving 1 surviving bot.

In the fifth operation, bot 2 drinks 3 bottles of original flavor iced black tea.

In the sixth operation, bot 2 has consecutively drunk 6 bottles of original flavor iced black tea and is destroyed, leaving no surviving bots.

Data Range

This problem uses bundled testing.

• Subtask 1 (5pts): $n, q \le 10^3$.
• Subtask 2 (20pts): All $k$ in operation 2 are $\le 20$.
• Subtask 3 (25pts): Data is guaranteed to be randomly generated.
• Subtask 4 (50pts): No special restrictions.

The test data generation method for Subtask 3 is as follows:

1. For each operation or query, choose one of the three types with equal probability.
2. If the chosen operation is not type 3, generate two numbers $l, r$ from $\left[1, n\right]$ with equal probability. If $l > r$, swap $l, r$, and use $l, r$ as the parameters for the operation.
3. If the chosen operation is not type 3, generate a number $k$ from $\left[1, 10^6\right]$ with equal probability as the parameter for the operation.

For all data, it is guaranteed that $1 \le n, q \le 2 \times 10^5$, $1 \le k \le 10^6$.

见题面 Input 部分

见题面 Output 部分