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 mod = 1e9 + 7;
const int maxm = 1e5 + 10;
const int inf = 0x3f3f3f3f;
namespace io {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
int f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char x) {
  *oS++ = x;
  if (oS == oT) flush();
}
template <typename A>
inline bool read(A &x) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (x = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    x = x * 10 + (c & 15);
  x *= f;
  return 1;
}
inline bool read(char &x) {
  while ((x = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                           (iS == iT ? EOF : *iS++))
                        : *iS++)) == ' ' ||
         x == '\n' || x == '\r')
    ;
  return x != EOF;
}
inline bool read(char *x) {
  while ((*x = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                            (iS == iT ? EOF : *iS++))
                         : *iS++)) == '\n' ||
         *x == ' ' || *x == '\r')
    ;
  if (*x == EOF) return 0;
  while (!(*x == '\n' || *x == ' ' || *x == '\r' || *x == EOF))
    *(++x) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                          (iS == iT ? EOF : *iS++))
                       : *iS++);
  *x = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &x, B &...y) {
  return read(x) && read(y...);
}
template <typename A>
inline bool write(A x) {
  if (!x) putc('0');
  if (x < 0) putc('-'), x = -x;
  while (x) qu[++qr] = x % 10 + '0', x /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char x) {
  putc(x);
  return 0;
}
inline bool write(const char *x) {
  while (*x) {
    putc(*x);
    ++x;
  }
  return 0;
}
inline bool write(char *x) {
  while (*x) {
    putc(*x);
    ++x;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A x, B... y) {
  return write(x) || write(y...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
struct node {
  int fmax, smax, maxnum, fmin, smin, minnum, flag1, flag2;
  long long ans;
} tree[maxm << 2];
void pushup(int rt) {
  tree[rt].ans = tree[rt << 1].ans + tree[rt << 1 | 1].ans;
  tree[rt].flag1 = tree[rt << 1].flag1 & tree[rt << 1 | 1].flag1;
  tree[rt].flag2 = tree[rt << 1].flag2 & tree[rt << 1 | 1].flag2;
  if (tree[rt << 1].fmax > tree[rt << 1 | 1].fmax) {
    tree[rt].fmax = tree[rt << 1].fmax;
    tree[rt].maxnum = tree[rt << 1].maxnum;
    tree[rt].smax = max(tree[rt << 1].smax, tree[rt << 1 | 1].fmax);
  } else if (tree[rt << 1].fmax < tree[rt << 1 | 1].fmax) {
    tree[rt].fmax = tree[rt << 1 | 1].fmax;
    tree[rt].maxnum = tree[rt << 1 | 1].maxnum;
    tree[rt].smax = max(tree[rt << 1 | 1].smax, tree[rt << 1].fmax);
  } else {
    tree[rt].fmax = tree[rt << 1].fmax;
    tree[rt].maxnum = tree[rt << 1].maxnum + tree[rt << 1 | 1].maxnum;
    tree[rt].smax = max(tree[rt << 1].smax, tree[rt << 1 | 1].smax);
  }
  if (tree[rt << 1].fmin < tree[rt << 1 | 1].fmin) {
    tree[rt].fmin = tree[rt << 1].fmin;
    tree[rt].minnum = tree[rt << 1].minnum;
    tree[rt].smin = min(tree[rt << 1].smin, tree[rt << 1 | 1].fmin);
  } else if (tree[rt << 1].fmin > tree[rt << 1 | 1].fmin) {
    tree[rt].fmin = tree[rt << 1 | 1].fmin;
    tree[rt].minnum = tree[rt << 1 | 1].minnum;
    tree[rt].smin = min(tree[rt << 1 | 1].smin, tree[rt << 1].fmin);
  } else {
    tree[rt].fmin = tree[rt << 1].fmin;
    tree[rt].minnum = tree[rt << 1].minnum + tree[rt << 1 | 1].minnum;
    tree[rt].smin = min(tree[rt << 1].smin, tree[rt << 1 | 1].smin);
  }
}
void build(int l, int r, int rt) {
  if (l == r) {
    tree[rt].fmax = inf;
    tree[rt].fmin = -inf;
    return;
  }
  int mid = l + r >> 1;
  build(l, mid, rt << 1);
  build(mid + 1, r, rt << 1 | 1);
  pushup(rt);
}
void uppos(int rt, int C) {
  tree[rt].ans -= 1ll * tree[rt].maxnum * (tree[rt].fmax - C);
  tree[rt].fmax = C;
}
void upneg(int rt, int C) {
  tree[rt].ans -= 1ll * tree[rt].minnum * (C - tree[rt].fmin);
  tree[rt].fmin = C;
}
void pushdown(int rt) {
  if (tree[rt << 1].fmax > tree[rt].fmax) uppos(rt << 1, tree[rt].fmax);
  if (tree[rt << 1 | 1].fmax > tree[rt].fmax) uppos(rt << 1 | 1, tree[rt].fmax);
  if (tree[rt << 1].fmin < tree[rt].fmin) upneg(rt << 1, tree[rt].fmin);
  if (tree[rt << 1 | 1].fmin < tree[rt].fmin) upneg(rt << 1 | 1, tree[rt].fmin);
}
void updatepos(int L, int R, int C, int l, int r, int rt) {
  if (L <= l && r <= R) {
    if (C >= tree[rt].fmax) return;
    if (C > tree[rt].smax && tree[rt].flag1) {
      uppos(rt, C);
      return;
    }
    if (l == r) {
      tree[rt].flag1 = 1;
      tree[rt].fmax = C;
      if (tree[rt].flag1 && tree[rt].flag2) {
        tree[rt].maxnum = tree[rt].minnum = 1;
        tree[rt].ans = tree[rt].fmax - tree[rt].fmin;
      }
      return;
    }
    int mid = l + r >> 1;
    pushdown(rt);
    updatepos(L, R, C, l, mid, rt << 1);
    updatepos(L, R, C, mid + 1, r, rt << 1 | 1);
    pushup(rt);
    return;
  }
  int mid = l + r >> 1;
  pushdown(rt);
  if (L <= mid) updatepos(L, R, C, l, mid, rt << 1);
  if (R > mid) updatepos(L, R, C, mid + 1, r, rt << 1 | 1);
  pushup(rt);
  return;
}
void updateneg(int L, int R, int C, int l, int r, int rt) {
  if (L <= l && r <= R) {
    if (C <= tree[rt].fmin) return;
    if (C < tree[rt].smin && tree[rt].flag2) {
      upneg(rt, C);
      return;
    }
    if (l == r) {
      tree[rt].flag2 = 1;
      tree[rt].fmin = C;
      if (tree[rt].flag1 && tree[rt].flag2) {
        tree[rt].maxnum = tree[rt].minnum = 1;
        tree[rt].ans = tree[rt].fmax - tree[rt].fmin;
      }
      return;
    }
    int mid = l + r >> 1;
    pushdown(rt);
    updateneg(L, R, C, l, mid, rt << 1);
    updateneg(L, R, C, mid + 1, r, rt << 1 | 1);
    pushup(rt);
    return;
  }
  int mid = l + r >> 1;
  pushdown(rt);
  if (L <= mid) updateneg(L, R, C, l, mid, rt << 1);
  if (R > mid) updateneg(L, R, C, mid + 1, r, rt << 1 | 1);
  pushup(rt);
  return;
}
long long query(int L, int R, int l, int r, int rt) {
  if (L <= l && r <= R) {
    return tree[rt].ans;
  }
  int mid = l + r >> 1;
  pushdown(rt);
  long long ans = 0;
  if (L <= mid) ans += query(L, R, l, mid, rt << 1);
  if (R > mid) ans += query(L, R, mid + 1, r, rt << 1 | 1);
  return ans;
}
int main() {
  int Q;
  read(Q);
  int n = 1e5;
  build(1, n, 1);
  while (Q--) {
    int op, l, r;
    read(op, l, r);
    r--;
    if (op == 1) {
      int k;
      read(k);
      if (k > 0)
        updatepos(l, r, k, 1, n, 1);
      else
        updateneg(l, r, k, 1, n, 1);
    } else
      printf("%lld\n", query(l, r, 1, n, 1));
  }
  return 0;
}
