Note

There are no lies or hidden elements anywhere in this problem.

Problem Statement

A multiset of intervals is called a good set if, for every real number $k$ with $0\leq k\lt L$, the set contains an interval that contains $k$.

There is a multiset $s$ of intervals, and initially $s$ is empty. You are given $Q$ queries; process them in order. Each query is in one of the following $2$ formats.

• 1 l r c: Add $c$ copies of the interval $[l:r)$ to $s$.
• 2 l r c: Remove $c$ copies of the interval $[l:r)$ from $s$. It is guaranteed that at this point $s$ contains at least $c$ copies of the interval $[l:r)$.

Here, the interval $[l:r)$ refers to the interval that contains all real numbers $k$ with $l\leq k\lt r$ and no other real numbers.

Also, each time you process a query, find the answer to the following problem.

• Find the maximum number of times the following operation can be performed.
  • $s$ has some of its elements chosen and removed. The multiset consisting of the chosen elements must be a good set.

Input

$Q$ $L$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

• $1\leq Q,L\leq 2\times 10^5$
• $0\leq l\lt r\leq L$
• $1\leq c\leq 10^9$
• For a query of the form 2 l r c, $s$ contains at least $c$ copies of the interval $[l:r)$
• All input values are integers

Output

Output $Q$ lines.

On line $i$, output the answer to the problem immediately after processing the $i$-th query.

Sample

8 3
1 0 2 1
1 1 3 2
1 0 1 2
1 2 3 1
2 0 2 1
2 1 3 1
2 0 1 1
2 2 3 1

0
1
2
3
2
1
1
1

Note

There really are no lies or hidden elements anywhere in this problem.