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 maxn = 1e5 + 10;
const int inf = 1e9 + 7;
int K, arr[maxn];
int id, ok, k;
struct SQ {
  static const int sq = 500;
  struct FenvTree {
    long long B[maxn >> 1];
    int ct[maxn >> 1];
    int n;
    void init(int _n) { n = _n; }
    void add(int pos, long long dl, int d) {
      for (int x = pos; x >= 0; x = (x & (x + 1)) - 1) {
        B[x] += dl, ct[x] += d;
      }
    }
    pair<long long, int> get(int pos) {
      long long res = 0ll;
      int Ct = 0;
      for (int x = pos; x < n; x |= (x + 1)) {
        res += B[x], Ct += ct[x];
      }
      return make_pair(res, Ct);
    }
  } f[2];
  int mn[2], a[2][sq], i;
  bool vis[2], Can[2][sq], iF[sq];
  set<int> can[2];
  long long sum;
  set<int> seq;
  set<int>::iterator it;
  void init() {
    for (i = 0; i < sq; i++) a[1][i] = a[0][i] = inf, seq.insert(i);
    mn[0] = mn[1] = inf;
    sum = 0;
    f[0].init(K);
    f[1].init(K);
  }
  void snake() {
    int w, o = ok ^ 1;
    if (mn[ok] <= id) return;
    pair<long long, int> ct = f[ok].get(id + 1);
    sum -= ct.first;
    sum += 1ll * k * ct.second;
    f[ok].add(id, 1ll * k * ct.second - ct.first, 0);
    mn[ok] = id;
    for (it = can[o].begin(); it != can[o].end(); it++) {
      w = *it;
      seq.erase(w);
      a[0][w] = min(a[0][w], mn[0]);
      a[1][w] = min(a[1][w], mn[1]);
      f[0].add(a[0][w], arr[a[0][w]], 1);
      f[1].add(a[1][w], arr[a[1][w]], 1);
      ct = f[1].get(1);
      iF[w] = 1;
      sum += arr[a[0][w]];
      sum += arr[a[1][w]];
    }
    can[o].clear();
    if (vis[ok]) return;
    vis[ok] = 1;
    for (it = seq.begin(); it != seq.end(); it++) {
      w = *it;
      if (Can[ok][w]) continue;
      Can[ok][w] = 1;
      can[ok].insert(w);
    }
  }
  void Snake(int p) {
    a[ok][p] = min(a[ok][p], mn[ok]);
    if (a[ok][p] <= id) return;
    int pr = a[ok][p];
    a[ok][p] = id;
    if (iF[p]) {
      sum -= arr[pr];
      sum += k;
      f[ok].add(pr, -arr[pr], -1);
      f[ok].add(id, k, 1);
    } else if (Can[ok ^ 1][p]) {
      can[ok ^ 1].erase(p);
      seq.erase(p);
      a[0][p] = min(a[0][p], mn[0]);
      a[1][p] = min(a[1][p], mn[1]);
      sum += arr[a[0][p]];
      sum += arr[a[1][p]];
      f[0].add(a[0][p], arr[a[0][p]], 1);
      f[1].add(a[1][p], arr[a[1][p]], 1);
      iF[p] = 1;
    } else if (!Can[ok][p]) {
      Can[ok][p] = 1;
      can[ok].insert(p);
    }
  }
  int get(int p) {
    if (iF[p]) {
      a[0][p] = min(a[0][p], mn[0]);
      a[1][p] = min(a[1][p], mn[1]);
      return arr[a[1][p]] + arr[a[0][p]];
    } else
      return 0;
  }
} sq[200];
int q_id[maxn], i, j, q;
int tp[maxn], l[maxn], r[maxn], val[maxn], L, R, pos[maxn], O[maxn];
int car[maxn], lid, rid;
int main() {
  scanf("%d", &q);
  for (i = 0; i < q; i++) {
    scanf("%d%d%d", tp + i, l + i, r + i);
    r[i]--;
    if (tp[i] == 1) {
      scanf("%d", val + i);
      if (val[i] < 0) val[i] = -val[i], O[i] = 1;
      arr[K++] = val[i];
    }
  }
  sort(arr, arr + K);
  K = unique(arr, arr + K) - arr;
  j = 1;
  for (i = 0; i < 200; i++) {
    k = 500;
    pos[i] = j;
    while (k--) {
      car[j] = (j - 1) % 500;
      q_id[j++] = i;
    }
    sq[i].init();
  }
  for (i = 0; i < q; i++) {
    lid = q_id[l[i]];
    rid = q_id[r[i]];
    L = l[i];
    R = r[i];
    if (tp[i] == 1) {
      k = val[i];
      ok = O[i];
      id = lower_bound(arr, arr + K, k) - arr;
      if (lid == rid) {
        while (L <= R) {
          sq[lid].Snake(car[L]);
          L++;
        }
        continue;
      }
      if (car[L]) {
        while (q_id[L] == lid) {
          sq[lid].Snake(car[L]);
          L++;
        }
        lid++;
      }
      if (car[R] < 499) {
        while (q_id[R] == rid) {
          sq[rid].Snake(car[R]);
          R--;
        }
        rid--;
      }
      while (lid <= rid) {
        sq[lid].snake();
        lid++;
      }
    } else {
      long long res = 0;
      if (lid == rid) {
        while (L <= R) {
          res += sq[lid].get(car[L]);
          L++;
        }
      } else {
        if (car[L]) {
          while (q_id[L] == lid) {
            res += sq[lid].get(car[L]);
            L++;
          }
          lid++;
        }
        if (car[R] < 499) {
          while (q_id[R] == rid) {
            res += sq[rid].get(car[R]);
            R--;
          }
          rid--;
        }
        while (lid <= rid) {
          res += sq[lid].sum;
          lid++;
        }
      }
      printf("%I64d\n", res);
    }
  }
  return 0;
}
