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 IINF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fll;
const double DINF = numeric_limits<double>::infinity();
const int MOD = 1000000007;
const double EPS = 1e-9;
const int DX[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int DY[] = {0, 1, 0, -1, 1, -1, -1, 1};
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long sqr(long long x) { return x * x; }
long long sqr(int x) { return (long long)x * x; }
double sqr(double x) { return x * x; }
long double sqr(long double x) { return x * x; }
mt19937 mmtw(960172);
long long rnd(long long x, long long y) {
  static uniform_int_distribution<long long> d;
  return d(mmtw) % (y - x + 1) + x;
}
const int N = 100899;
const int S = 333;
struct Block1 {
  pair<int, int> a[S];
  int th;
  int pos;
  long long sumg;
  bool *good;
  int cntg;
  int arr[S];
  Block1() {
    th = IINF;
    for (int i = 0; i < S; ++i) a[i] = {arr[i] = IINF, i};
    sumg = 0;
    cntg = 0;
    pos = S;
  }
  void newTH(int nth) {
    if (nth >= th) return;
    if (th == IINF)
      sumg += 1LL * (nth)*cntg;
    else
      sumg += 1LL * (nth - th) * cntg;
    th = nth;
    while (pos > 0 && a[pos - 1].first >= th) {
      --pos;
      if (good[a[pos].second]) {
        ++cntg;
        if (a[pos].first == IINF) {
          sumg += th;
        } else {
          sumg += th - a[pos].first;
        }
      }
    }
  }
  void snake(int v, int l, int r) {
    if (l >= S || r < 0 || v >= th) return;
    if (l <= 0 && S - 1 <= r) {
      newTH(v);
      return;
    }
    static pair<int, int> s1[S], s2[S];
    int s1s = 0, s2s = 0;
    for (int i = 0; i < S; ++i)
      if (l <= a[i].second && a[i].second <= r)
        s1[s1s++] = {min(a[i].first, v), a[i].second};
      else
        s2[s2s++] = {min(a[i].first, th), a[i].second};
    merge(s1, s1 + s1s, s2, s2 + s2s, a);
    th = IINF;
    pos = S;
    sumg = 0;
    cntg = 0;
    for (int i = 0; i < S; ++i)
      if (a[i].first != IINF) {
        arr[a[i].second] = a[i].first;
        if (good[a[i].second]) sumg += a[i].first;
      }
  }
};
bool good[N];
bool good1[N], good2[N];
struct Block2 {
  Block1 b1, b2;
  Block2() {}
  void snake(int v, int l, int r) {
    if (r < 0 || l >= S) return;
    if (v > 0)
      b1.snake(v, l, r);
    else
      b2.snake(-v, l, r);
  }
  long long sum(int l, int r) {
    if (r < 0 || l >= S) return 0;
    if (l <= 0 && S - 1 <= r) return b1.sumg + b2.sumg;
    long long ans = 0;
    l = max(l, 0);
    r = min(r, S - 1);
    for (int i = l; i <= r; ++i)
      if (b1.good[i]) {
        ans += min(b1.th, b1.arr[i]);
      }
    for (int i = l; i <= r; ++i)
      if (b1.good[i]) {
        ans += min(b2.th, b2.arr[i]);
      }
    return ans;
  }
} bb[N / S];
int q;
set<int> nogood1;
set<int> nogood2;
int main() {
  ios::sync_with_stdio(false);
  for (int i = 0; i < N; ++i) nogood1.insert(i);
  for (int i = 0; i < N; ++i) nogood2.insert(i);
  for (int i = 0; i < N / S; ++i) {
    bb[i].b1.good = good + i * S;
    bb[i].b2.good = good + i * S;
  }
  cin >> q;
  for (int i = 0; i < q; ++i) {
    int t, l, r;
    cin >> t >> l >> r;
    --r;
    if (t == 1) {
      long long y;
      cin >> y;
      for (int j = 0; j < N / S; ++j) bb[j].snake(y, l - j * S, r - j * S);
      auto &ng = (y > 0 ? nogood1 : nogood2);
      bool *cgood = (y > 0 ? good1 : good2);
      while (true) {
        auto it = ng.lower_bound(l);
        if (it == ng.end() || *it > r) break;
        int ii = *it;
        ng.erase(it);
        cgood[ii] = true;
        if (good1[ii] && good2[ii] && !good[ii]) {
          good[ii] = true;
          Block1 &b1 = bb[ii / S].b1;
          int val = min(b1.arr[ii % S], b1.th);
          if (val != IINF) {
            b1.sumg += val;
          }
          if (b1.arr[ii % S] >= b1.th) ++b1.cntg;
          Block1 &b2 = bb[ii / S].b2;
          val = min(b2.arr[ii % S], b2.th);
          if (val != IINF) {
            b2.sumg += val;
          }
          if (b2.arr[ii % S] >= b2.th) ++b2.cntg;
        }
      }
    } else {
      long long ans = 0;
      for (int j = 0; j < N / S; ++j) ans += bb[j].sum(l - j * S, r - j * S);
      cout << ans << "\n";
    }
  }
  return 0;
}
