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

Input

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

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

Note

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