纳吉尼是神秘人因谋杀伯莎·乔金斯而创造的魂器,它已经集结了蛇大军,正在对霍格沃茨学校发动攻击。
霍格沃茨的入口可以想象为一条从 1 到 105 的直线(x 轴)。纳吉尼正在霍格沃茨入口处发射各种蛇。每条蛇平行于入口着陆,覆盖从 x = l 到 x = r 距离为 k 的一段。形式上,每条蛇可以想象为点 (l, k) 和 (r, k) 之间的线段。请注意,k 可以为正值,也可以为负值,但不能为 0。
设,在某个 x 坐标 x = i 处,点 (i, y1) 和点 (i, y2) 处存在蛇,使得 y1 > 0 且 y2 < 0。那么,如果对于包含蛇的任何点 (i, y3),使得 y3 > 0,则 y1 ≤ y3 成立,并且对于包含蛇的任何点,使得 y4 < 0, |y2| ≤ |y4|成立,则坐标 x = i 处的危险值为 y1 + |y2|。如果不存在这样的y1和y2,则危险值为0。
哈利想要计算霍格沃茨入口各个部分的危险值。入口段 [l, r) 的危险值可以通过对段中存在的每个整数 x 坐标的危险值求和来计算。
正式来说,您必须实现两种类型的查询:
- 1 l r k:在 y 坐标 y 坐标 y = k(包括 l,不包括 r)处,从 x = l 到 x = r 处平行于入口添加一条蛇。
- 2 l r:您必须计算段l到r的危险值(包括l,不包括r)。
输入
输入的第一行包含一个整数 q (1 ≤ q ≤ 5·104),表示查询数量。
接下来的 q 行每行描述一个查询。每个查询描述首先包含查询类型 typei (1 ≤ typei ≤ 2)。接下来是查询的进一步描述。如果类型为 1,则后面跟着整数 li、ri 和 ki ($$1 \leq l_i < r_i \leq 10^5$$, - 109 ≤ ki ≤ 109,k ≠ 0)。否则,它只包含两个整数 li 和 ri (1 ≤ li < ri ≤ 105)。
输出
在单独的行中输出类型 2 的每个查询的答案。
示例
输入 #1
3 1 1 10 10 1 2 4 -7 2 1 10
输出 #1
34
输入 #2
7 1 2 3 5 1 1 10 10 1 4 5 -5 2 4 8 1 1 10 -10 2 4 8 2 1 10
输出 #2
15 75 170
注意
在第一个示例案例中,x 坐标 1 的危险值为 0,因为没有 y2 满足 x = 1 的上述条件。
x 坐标 2 和 3 的危险值为 10 + | - 7| = 17。
x 坐标 4 到 9 的危险值再次为 0,因为这些坐标没有满足上述条件的 y2。
因此,总危险值为 17 + 17 = 34。