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, y1) and point (i, y2), such that y1 > 0 and y2 < 0. Then, if for any point (i, y3) containing a snake such that y3 > 0, y1 ≤ y3 holds and for any point (i, y4) containing a snake such that y4 < 0, |y2| ≤ |y4| holds, then the danger value at coordinate x = i is y1 + |y2|. If no such y1 and y2 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 typei (1 ≤ typei ≤ 2). This is followed by further description of the query. In case of the type being 1, it is followed by integers li, ri and ki (<image>,  - 109 ≤ ki ≤ 109, k ≠ 0). Otherwise, it just contains two integers, li and ri (1 ≤ li < ri ≤ 105).

Output

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

Examples

Input

3
1 1 10 10
1 2 4 -7
2 1 10


Output

34


Input

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


Output

15
75
170

Note

In the first sample case, the danger value for x-coordinates 1 is 0 as there is no y2 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 y2 satisfying the above condition for these coordinates.

Thus, total danger value is 17 + 17 = 34.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int n = 1e5;
const int inf = 1e9 + 10;
inline int read() {
  int ret = 0, flag = 1;
  char c = getchar();
  while (!isdigit(c)) flag = c == '-' ? -1 : 1, c = getchar();
  while (isdigit(c)) ret = ret * 10 + c - '0', c = getchar();
  return ret * flag;
}
struct segment {
  int mx[N << 2], cx[N << 2], laz[N << 2], exs[N << 2], nm[N << 2];
  long long sum[N << 2];
  inline void modify(int rt, int z) {
    sum[rt] -= 1ll * exs[rt] * nm[rt] * mx[rt];
    laz[rt] = min(laz[rt], z);
    mx[rt] = min(mx[rt], z);
    sum[rt] += 1ll * (exs[rt] = 1) * nm[rt] * mx[rt];
  }
  inline void check(int rt, int z) {
    if (z > mx[rt])
      swap(mx[rt], cx[rt]), swap(mx[rt], z);
    else if ((z ^ mx[rt]) && (z > cx[rt]))
      swap(z, cx[rt]);
  }
  inline void pushup(int rt) {
    exs[rt] = exs[(rt << 1)] & exs[((rt << 1) | 1)];
    sum[rt] = sum[(rt << 1)] + sum[((rt << 1) | 1)];
    mx[rt] = mx[(rt << 1)], cx[rt] = cx[(rt << 1)];
    check(rt, mx[((rt << 1) | 1)]), check(rt, cx[((rt << 1) | 1)]);
    nm[rt] = (mx[rt] == mx[(rt << 1)]) * nm[(rt << 1)] +
             (mx[rt] == mx[((rt << 1) | 1)]) * nm[((rt << 1) | 1)];
  }
  inline void pushdown(int rt) {
    if (!(laz[rt] ^ inf)) return;
    modify((rt << 1), laz[rt]), modify(((rt << 1) | 1), laz[rt]), laz[rt] = inf;
  }
  void build(int rt, int l, int r) {
    laz[rt] = mx[rt] = inf;
    cx[rt] = -inf;
    nm[rt] = r - l + 1;
    sum[rt] = exs[rt] = 0;
    if (l == r) return;
    build((rt << 1), l, ((l + r) >> 1));
    build(((rt << 1) | 1), ((l + r) >> 1) + 1, r);
  }
  void change(int rt, int l, int r, int L, int R, int z) {
    if (L <= l && r <= R) {
      if (mx[rt] <= z)
        return;
      else if (z >= cx[rt]) {
        modify(rt, z);
        return;
      }
    }
    pushdown(rt);
    if (L <= ((l + r) >> 1)) change((rt << 1), l, ((l + r) >> 1), L, R, z);
    if (((l + r) >> 1) < R)
      change(((rt << 1) | 1), ((l + r) >> 1) + 1, r, L, R, z);
    pushup(rt);
  }
} T[2];
long long query(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    if (T[0].exs[rt] && T[1].exs[rt]) return T[0].sum[rt] + T[1].sum[rt];
    if (l == r || !T[0].sum[rt] || !T[1].sum[rt]) return 0;
  }
  T[0].pushdown(rt);
  T[1].pushdown(rt);
  long long ret = 0;
  if (L <= ((l + r) >> 1)) ret = query((rt << 1), l, ((l + r) >> 1), L, R);
  if (((l + r) >> 1) < R)
    ret += query(((rt << 1) | 1), ((l + r) >> 1) + 1, r, L, R);
  return ret;
}
int main() {
  int t, x, y, z, Q;
  T[0].build(1, 1, n);
  T[1].build(1, 1, n);
  for (Q = read(); Q--;) {
    t = read(), x = read(), y = read();
    --y;
    if (t == 1)
      z = read(), T[z > 0].change(1, 1, n, x, y, abs(z));
    else
      printf("%lld\n", query(1, 1, n, x, y));
  }
  return 0;
}
