Dynamic Bot Maintenance

There are \(n\) bots arranged in a line. Every day, each bot drinks iced tea. We need to dynamically maintain the status of the bots under the following three types of operations:

• 1 l r k: For every alive bot, if its index \(i\) belongs to \([l, r]\) then it drinks \(k\) bottles of original iced tea; otherwise it drinks \(k\) bottles of tropical iced tea. (In other words, for every alive bot, update its last consumed tea flavor and bottle count accordingly.)
• 2 l r k: The BTC administrator, in anger, destroys the bots in the subarray \([l, r]\) that form the last contiguous block (by index) of alive bots drinking the same flavored iced tea. More precisely, among alive bots in \([l, r]\), let \(p\) be the rightmost alive bot. Then, moving left from \(p\), count the consecutive alive bots having the same flavor as bot \(p\). If the count is at least \(k\), all of those bots are destroyed. Note that destruction does not change the numbering of the bots.
• 3: Query the current number of alive bots.

Input Format: The first line contains two integers \(n\) and \(q\) (the number of bots and the number of operations). The next \(q\) lines each contain an operation in one of the three formats described above.

Note: A bot that is destroyed will no longer be updated or counted in queries.

inputFormat

The first line contains two integers \(n\) and \(q\) — the number of bots and the number of operations.

Each of the following \(q\) lines contains an operation in one of the following formats:

• 1 l r k
• 2 l r k
• 3

For operation 1, bots in the range \([l, r]\) are updated to have flavor original and consume \(k\) bottles, while bots outside the range (if still alive) are updated to have flavor tropical and consume \(k\) bottles.

For operation 2, among all alive bots in the subarray \([l, r]\), let \(p\) be the rightmost alive bot. Then, the contiguous block of alive bots ending at \(p\) that share the same flavor is considered. If the size of this block is at least \(k\), all bots in that block are destroyed.

Operation 3 queries and prints the number of alive bots.

outputFormat

For each operation of type 3, output a single line containing the number of alive bots.

sample

5 6
1 2 4 3
3
2 1 5 2
3
2 2 5 1
3

5
5
4