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;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int a[100000 + 350 + 5], b[100000 + 350 + 5], u[100000 + 350 + 5],
    pa[100000 + 350 + 5], pb[100000 + 350 + 5];
int ra[100000 + 5], rb[100000 + 5], ca[100000 + 5], cb[100000 + 5],
    usa[100000 + 350 + 5], usb[100000 + 350 + 5];
long long sa[100000 + 350 + 5], sb[100000 + 350 + 5], ans[100000 + 5];
bool cmpa(int x, int y) { return a[x] < a[y]; }
bool cmpb(int x, int y) { return b[x] < b[y]; }
void build(int x) {
  ans[x] = 0;
  for (int i = x; i < x + 350; ++i)
    pa[i] = pb[i] = i,
    ans[x] += (u[i] = a[i] < 1000000001 && b[i] < 1000000001) ? a[i] + b[i] : 0;
  sort(pa + x, pa + x + 350, cmpa);
  sort(pb + x, pb + x + 350, cmpb);
  ra[x] = rb[x] = x + 350 - 1;
  ca[x] = a[pa[x + 350 - 1]];
  cb[x] = b[pb[x + 350 - 1]];
  for (int i = x + 350; i-- > x;)
    usa[i] = (i + 1 < x + 350 ? usa[i + 1] : 0) + u[pa[i]],
    sa[i] = (i + 1 < x + 350 ? sa[i + 1] : 0) + u[pa[i]] * a[pa[i]],
    usb[i] = (i + 1 < x + 350 ? usb[i + 1] : 0) + u[pb[i]],
    sb[i] = (i + 1 < x + 350 ? sb[i + 1] : 0) + u[pb[i]] * b[pb[i]];
}
void rebuild(int x) {
  for (int i = ra[x]; i < x + 350; ++i) a[pa[i]] = ca[x];
  for (int i = rb[x]; i < x + 350; ++i) b[pb[i]] = cb[x];
}
void mark(int x, int z) {
  int l, r, mid, res = 0;
  if (z > 0) {
    if (z >= ca[x]) return;
    for (l = x, r = ra[x] - 1; l <= r;)
      if (z < a[pa[mid = l + r >> 1]])
        res = mid, r = mid - 1;
      else
        l = mid + 1;
    if (res) ans[x] += 1LL * z * (usa[res] - usa[ra[x]]) - sa[res] + sa[ra[x]];
    ans[x] += 1LL * usa[ra[x]] * (z - ca[x]);
    ra[x] = res ? res : ra[x];
    ca[x] = z;
  } else {
    if ((z = -z) >= cb[x]) return;
    for (l = x, r = rb[x] - 1; l <= r;)
      if (z < b[pb[mid = l + r >> 1]])
        res = mid, r = mid - 1;
      else
        l = mid + 1;
    if (res) ans[x] += 1LL * z * (usb[res] - usb[rb[x]]) - sb[res] + sb[rb[x]];
    ans[x] += 1LL * usb[rb[x]] * (z - cb[x]);
    rb[x] = res ? res : rb[x];
    cb[x] = z;
  }
}
int main() {
  int q = read(), t, l, r, x, i, j, lk, rk;
  for (i = 1; i < 100000; ++i) a[i] = b[i] = 1000000001;
  for (i = 1; i < 100000; i += 350) build(i);
  while (q--) {
    t = read();
    l = read();
    r = read() - 1;
    lk = (l - 1) / 350 * 350 + 1;
    rk = (r - 1) / 350 * 350 + 1;
    if (t == 1) {
      x = read();
      rebuild(lk);
      if (lk != rk) rebuild(rk);
      for (i = l; i < lk + 350 && i <= r; ++i)
        if (x > 0)
          a[i] = min(a[i], x);
        else
          b[i] = min(b[i], -x);
      if (lk != rk)
        for (i = r; i >= rk; --i)
          if (x > 0)
            a[i] = min(a[i], x);
          else
            b[i] = min(b[i], -x);
      build(lk);
      if (lk != rk) build(rk);
      for (i = lk + 350; i < rk; i += 350)
        if (x > 0 && ca[i] == 1000000001) {
          rebuild(i);
          for (j = i; j < i + 350; ++j) a[j] = min(a[j], x);
          build(i);
        } else if (x < 0 && cb[i] == 1000000001) {
          rebuild(i);
          for (j = i; j < i + 350; ++j) b[j] = min(b[j], -x);
          build(i);
        } else
          mark(i, x);
    } else {
      long long res = 0;
      rebuild(lk);
      if (lk != rk) rebuild(rk);
      for (i = l; i < lk + 350 && i <= r; ++i)
        res += a[i] < 1000000001 && b[i] < 1000000001 ? a[i] + b[i] : 0;
      if (lk != rk)
        for (i = r; i >= rk; --i)
          res += a[i] < 1000000001 && b[i] < 1000000001 ? a[i] + b[i] : 0;
      build(lk);
      if (lk != rk) build(rk);
      for (i = lk + 350; i < rk; i += 350) res += ans[i];
      printf("%I64d\n", res);
    }
  }
}
