CF855F.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.

In the first sample case, the danger value for $x$ -coordinates $1$ is $0$ as there is no $y_{2}$ satisfying the above condition for $x=1$ .

Danger values for $x$ -coordinates $2$ and $3$ is $10+|-7|=17$ .

Danger values for $x$ -coordinates $4$ to $9$ is again $0$ as there is no $y_{2}$ satisfying the above condition for these coordinates.

Thus, total danger value is $17+17=34$ .