A11250 | Nagini

Nagini, being a horcrux You-know-who created with the murder of Bertha Jorkins, has accumulated its army of snakes and is launching an attack on Hogwarts school.

Hogwarts' entrance can be imagined as a straight line (x-axis) from $1$ to $10^{5}$ . Nagini is launching various snakes at the Hogwarts entrance. Each snake lands parallel to the entrance, covering a segment at a distance $k$ from $x=l$ to $x=r$ . Formally, each snake can be imagined as being a line segment between points $(l,k)$ and $(r,k)$ . Note that $k$ can be both positive and negative, but not $0$ .

Let, at some $x$ -coordinate $x=i$ , there be snakes at point $(i,y_{1})$ and point $(i,y_{2})$ , such that $y_{1}>0$ and $y_{2}<0$ . Then, if for any point $(i,y_{3})$ containing a snake such that $y_{3}>0$ , $y_{1}<=y_{3}$ holds and for any point $(i,y_{4})$ containing a snake such that $y_{4}<0$ , $|y_{2}|<=|y_{4}|$ holds, then the danger value at coordinate $x=i$ is $y_{1}+|y_{2}|$ . If no such $y_{1}$ and $y_{2}$ exist, danger value is $0$ .

Harry wants to calculate the danger value of various segments of the Hogwarts entrance. Danger value for a segment $[l,r)$ of the entrance can be calculated by taking the sum of danger values for each integer $x$ -coordinate present in the segment.

Formally, you have to implement two types of queries:

- 1 l r k: a snake is added parallel to entrance from $x=l$ to $x=r$ at y-coordinate $y=k$ ( $l$ inclusive, $r$ exclusive).
- 2 l r: you have to calculate the danger value of segment $l$ to $r$ ( $l$ inclusive, $r$ exclusive).

First line of input contains a single integer $q$ ( $1<=q<=5·10^{4}$ ) denoting the number of queries.

Next $q$ lines each describe a query. Each query description first contains the query type $type_{i}$ ( $1<=type_{i}<=2$ ). This is followed by further description of the query. In case of the type being $1$ , it is followed by integers $l_{i},r_{i}$ and $k_{i}$ (, $-10^{9}<=k_{i}<=10^{9}$ , $k≠0$ ). Otherwise, it just contains two integers, $l_{i}$ and $r_{i}$ ( $1<=l_{i}<r_{i}<=10^{5}$ ).

Output the answer for each query of type 2 in a separate line.