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⁵. 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₁) and point (i, y₂), such that y₁ > 0 and y₂ < 0. Then, if for any point (i, y₃) containing a snake such that y₃ > 0, y₁ ≤ y₃ holds and for any point (i, y₄) containing a snake such that y₄ < 0, |y₂| ≤ |y₄| holds, then the danger value at coordinate x = i is y₁ + |y₂|. If no such y₁ and y₂ 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⁴) 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⁹ ≤ k_i ≤ 10⁹, k ≠ 0). Otherwise, it just contains two integers, l_i and r_i (1 ≤ l_i < r_i ≤ 10⁵).

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