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 105. 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·104) 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_ (, - 109 ≤ _k__i_ ≤ 109, _k_ ≠ 0). Otherwise, it just contains two integers, _l__i_ and _r__i_ (1 ≤ _l__i_ < _r__i_ ≤ 105).
## Output
Output the answer for each query of type 2 in a separate line.
[samples]
## 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.
Nagini 作为伏地魔用杀害伯莎·乔金斯所制造的魂器，已经集结了它的蛇群，并对霍格沃茨学校发动了攻击。
霍格沃茨的入口可以被想象为一条从 #cf_span[1] 到 #cf_span[105] 的直线（x 轴）。Nagini 正在向霍格沃茨入口发射各种蛇。每条蛇都平行于入口落地，覆盖在距离 #cf_span[x = l] 到 #cf_span[x = r] 处、距离为 #cf_span[k] 的线段上。形式上，每条蛇可以被看作连接点 #cf_span[(l, k)] 和 #cf_span[(r, k)] 的线段。注意，#cf_span[k] 可以为正或负，但不能为 #cf_span[0]。
设在某个 #cf_span[x]-坐标 #cf_span[x = i] 处，存在蛇位于点 #cf_span[(i, y1)] 和点 #cf_span[(i, y2)]，满足 #cf_span[y1 > 0] 且 #cf_span[y2 < 0]。那么，若对任意包含蛇的点 #cf_span[(i, y3)]（其中 #cf_span[y3 > 0]），均有 #cf_span[y1 ≤ y3] 成立，且对任意包含蛇的点 #cf_span[(i, y4)]（其中 #cf_span[y4 < 0]），均有 #cf_span[|y2| ≤ |y4|] 成立，则坐标 #cf_span[x = i] 的危险值为 #cf_span[y1 + |y2|]。若不存在满足上述条件的 #cf_span[y1] 和 #cf_span[y2]，则危险值为 #cf_span[0]。
哈利希望计算霍格沃茨入口各段的危险值。入口段 #cf_span[[l, r)] 的危险值可以通过对该段中每个整数 #cf_span[x]-坐标的危险值求和得到。
形式上，你需要实现两种类型的查询：
输入的第一行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 5·10^4]），表示查询数量。
接下来的 #cf_span[q] 行每行描述一个查询。每个查询首先包含查询类型 #cf_span[typei]（#cf_span[1 ≤ typei ≤ 2]）。随后是该查询的进一步描述：若类型为 #cf_span[1]，则后跟整数 #cf_span[li, ri] 和 #cf_span[ki]（#cf_span[ - 10^9 ≤ ki ≤ 10^9]，#cf_span[k ≠ 0]）；否则，仅包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li < ri ≤ 10^5]）。
对每个类型为 2 的查询，在单独一行输出答案。
在第一个样例中，#cf_span[x]-坐标 #cf_span[1] 的危险值为 #cf_span[0]，因为不存在满足上述条件的 #cf_span[y2]（当 #cf_span[x = 1] 时）。
#cf_span[x]-坐标 #cf_span[2] 和 #cf_span[3] 的危险值为 #cf_span[10 + | - 7| = 17]。
#cf_span[x]-坐标 #cf_span[4] 到 #cf_span[9] 的危险值再次为 #cf_span[0]，因为这些坐标上不存在满足条件的 #cf_span[y2]。
因此，总危险值为 #cf_span[17 + 17 = 34]。
## Input
输入的第一行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 5·10^4]），表示查询数量。接下来的 #cf_span[q] 行每行描述一个查询。每个查询首先包含查询类型 #cf_span[typei]（#cf_span[1 ≤ typei ≤ 2]）。随后是该查询的进一步描述：若类型为 #cf_span[1]，则后跟整数 #cf_span[li, ri] 和 #cf_span[ki]（#cf_span[ - 10^9 ≤ ki ≤ 10^9]，#cf_span[k ≠ 0]）；否则，仅包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li < ri ≤ 10^5]）。
## Output
对每个类型为 2 的查询，在单独一行输出答案。
[samples]
## Note
在第一个样例中，#cf_span[x]-坐标 #cf_span[1] 的危险值为 #cf_span[0]，因为不存在满足上述条件的 #cf_span[y2]（当 #cf_span[x = 1] 时）。#cf_span[x]-坐标 #cf_span[2] 和 #cf_span[3] 的危险值为 #cf_span[10 + | - 7| = 17]。#cf_span[x]-坐标 #cf_span[4] 到 #cf_span[9] 的危险值再次为 #cf_span[0]，因为这些坐标上不存在满足条件的 #cf_span[y2]。因此，总危险值为 #cf_span[17 + 17 = 34]。
**Definitions**
Let $ Q \in \mathbb{Z} $ be the number of queries.
Let $ S \subseteq \mathbb{Z} \times \mathbb{Z} $ be the set of snake segments, where each element $ (l, r, k) \in S $ represents a horizontal segment from $ (l, k) $ to $ (r, k) $, with $ k \ne 0 $.
For any integer coordinate $ x \in [1, 10^5] $:
- Let $ P_x = \{ k \mid (l, r, k) \in S \text{ and } l \le x < r \} $ be the set of vertical positions of snakes covering $ x $.
- Let $ P_x^+ = \{ k \in P_x \mid k > 0 \} $, $ P_x^- = \{ k \in P_x \mid k < 0 \} $.
- Define the **danger value** at $ x $ as:
$$
d(x) =
\begin{cases}
\max P_x^+ + |\min P_x^-| & \text{if } P_x^+ \ne \emptyset \text{ and } P_x^- \ne \emptyset, \\
0 & \text{otherwise}.
\end{cases}
$$
**Constraints**
1. $ 1 \le Q \le 5 \cdot 10^4 $
2. For each query:
- Type 1: $ 1 \le l_i < r_i \le 10^5 $, $ -10^9 \le k_i \le 10^9 $, $ k_i \ne 0 $
- Type 2: $ 1 \le l_i < r_i \le 10^5 $
**Objective**
For each query:
- If type 1: Add segment $ (l_i, r_i, k_i) $ to $ S $.
- If type 2: Compute $ \sum_{x = l_i}^{r_i - 1} d(x) $ and output the result.