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 Imx = 2147483647;
const long long Lbig = 2e18;
const int mod = 1e9 + 7;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c == ' ' || c == '\n') c = _buff.get();
  return c;
}
const int magic = 333;
int a[101111], b[101111];
bool f[101111], fa[101111], fb[101111];
struct BLOCK {
  int l, r;
  int tab[500], tbsz;
  long long sum[500];
  int tag;
  BLOCK() {
    tag = mod;
    tbsz = 0;
  }
  void reconstruct(int a[], bool ff[]) {
    if (tag != mod) {
      for (int i = l; i <= r; i++) {
        a[i] = min(a[i], tag);
        ff[i] = 1;
        f[i] = fa[i] & fb[i];
      }
    }
    tag = mod;
    tbsz = 0;
    for (int i = l; i <= r; i++) {
      if (!f[i]) continue;
      tab[tbsz++] = a[i];
    }
    sort(tab, tab + tbsz);
    tab[tbsz] = 0;
    sum[0] = tab[0];
    for (int i = 1; i <= tbsz; i++) sum[i] = sum[i - 1] + tab[i];
  }
  long long query() {
    if (tag == mod) return sum[tbsz];
    int pos = lower_bound(tab, tab + tbsz, tag) - tab - 1;
    if (pos == -1)
      return 1ll * tbsz * tag;
    else
      return sum[pos] + 1ll * (tbsz - pos - 1) * tag;
  }
  int mini(int x) { tag = min(tag, x); }
} A[555], B[555];
bool tga[500], tgb[500];
int q;
void updateA(int x) {
  A[x].reconstruct(a, fa);
  B[x].reconstruct(b, fb);
}
void updateB(int x) {
  B[x].reconstruct(b, fb);
  A[x].reconstruct(a, fa);
}
void miniA(int l, int r, int k) {
  int lg = l / magic;
  while (l / magic == lg && l <= r) {
    a[l] = min(a[l], k);
    fa[l] = 1;
    f[l] = fa[l] & fb[l];
    l++;
  }
  updateA(lg);
  while (l + magic - 1 <= r) {
    A[l / magic].mini(k);
    if (!tga[l / magic]) {
      updateA(l / magic);
      tga[l / magic] = 1;
    }
    l += magic;
  }
  while (l <= r) {
    a[l] = min(a[l], k);
    fa[l] = 1;
    f[l] = fa[l] & fb[l];
    l++;
  }
  if (r / magic != lg) updateA(r / magic);
}
void miniB(int l, int r, int k) {
  int lg = l / magic;
  while (l / magic == lg && l <= r) {
    b[l] = min(b[l], k);
    fb[l] = 1;
    f[l] = fa[l] & fb[l];
    l++;
  }
  updateA(lg);
  while (l + magic - 1 <= r) {
    B[l / magic].mini(k);
    if (!tgb[l / magic]) {
      updateB(l / magic);
      tgb[l / magic] = 1;
    }
    l += magic;
  }
  while (l <= r) {
    b[l] = min(b[l], k);
    fb[l] = 1;
    f[l] = fa[l] & fb[l];
    l++;
  }
  if (r / magic != lg) updateA(r / magic);
}
long long query(int l, int r) {
  long long ans = 0;
  int lg = l / magic;
  updateA(lg);
  while (l / magic == lg && l <= r) {
    if (f[l]) ans += a[l] + b[l];
    l++;
  }
  while (l + magic - 1 <= r) {
    ans += A[l / magic].query() + B[l / magic].query();
    l += magic;
  }
  if (r / magic != lg) updateA(r / magic);
  while (l <= r) {
    if (f[l]) ans += a[l] + b[l];
    l++;
  }
  return ans;
}
int main() {
  for (int i = 0; i < 101111; i++) a[i] = b[i] = mod;
  for (int i = 0; i <= min(500, 100000 / magic + 1); i++) {
    A[i].l = i * magic;
    A[i].r = (i + 1) * magic - 1;
    B[i].l = i * magic;
    B[i].r = (i + 1) * magic - 1;
  }
  q = getnum();
  for (int i = 1; i <= q; i++) {
    int cmd, l, r, k;
    cmd = getnum(), l = getnum(), r = getnum();
    r--;
    if (cmd == 1) {
      k = getnum();
      if (k < 0)
        miniB(l, r, -k);
      else
        miniA(l, r, k);
    } else {
      putnum(query(l, r)), putchar('\n');
    }
  }
  return 0;
}
