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 MAX = 1.1e9;
const int M = 300;
const int N = (100005 + M) / M * M;
long long SUM[N / M];
long long SUMPOS[N / M];
long long SUMNEG[N / M];
int POS[N / M];
int NEG[N / M];
int sum[N];
int pos[N];
int neg[N];
int spos[N];
int sneg[N];
long long sspos[N];
long long ssneg[N];
int sposall[N];
int snegall[N];
long long ssposall[N];
long long ssnegall[N];
int cntpos[N / M];
int cntneg[N / M];
int cnt[N / M];
void push(int x) {
  for (int i = x * M; i < (x + 1) * M; ++i) {
    pos[i] = min(pos[i], POS[x]);
    neg[i] = min(neg[i], NEG[x]);
    if (pos[i] < MAX && neg[i] < MAX) sum[i] = pos[i] + neg[i];
  }
}
void upd(int x, int y) {
  int ind = x / M;
  if (y > 0) {
    if (pos[x] < MAX) SUMPOS[ind] -= pos[x];
    pos[x] = min(pos[x], y);
    SUMPOS[ind] += pos[x];
  } else {
    if (neg[x] < MAX) SUMNEG[ind] -= neg[x];
    neg[x] = min(neg[x], -y);
    SUMNEG[ind] += neg[x];
  }
  SUM[ind] -= sum[x];
  if (pos[x] < MAX && neg[x] < MAX) sum[x] = pos[x] + neg[x];
  SUM[ind] += sum[x];
}
void build(int x) {
  int l = x * M, r = x * M + M;
  memcpy(sposall + l, pos + l, M * sizeof(pos[0]));
  memcpy(snegall + l, neg + l, M * sizeof(pos[0]));
  int it = 0;
  cntpos[x] = cntneg[x] = 0;
  for (int i = l; i < r; ++i) {
    if (pos[i] < MAX && neg[i] < MAX) {
      spos[l + it] = pos[i];
      sneg[l + it] = neg[i];
      ++it;
    }
    cntpos[x] += pos[i] < MAX;
    cntneg[x] += neg[i] < MAX;
  }
  cnt[x] = it;
  sort(spos + l, spos + l + cnt[x]);
  sort(sneg + l, sneg + l + cnt[x]);
  sort(sposall + l, sposall + r);
  sort(snegall + l, snegall + r);
  ssposall[l] = sposall[l];
  sspos[l] = spos[l];
  ssnegall[l] = snegall[l];
  ssneg[l] = sneg[l];
  for (int i = l + 1; i < l + cnt[x]; ++i) {
    sspos[i] = sspos[i - 1] + spos[i];
    ssneg[i] = ssneg[i - 1] + sneg[i];
  }
  for (int i = l + 1; i < r; ++i) {
    ssposall[i] = ssposall[i - 1] + sposall[i];
    ssnegall[i] = ssnegall[i - 1] + snegall[i];
  }
}
const int DEBUG = 0, S = 107, BAD = 41;
int stupidpos[N], stupidneg[N];
void calcs(int ind) {
  int l = ind * M, r = ind * M + M;
  if (POS[ind] < MAX && NEG[ind] < MAX) {
    int itpos = lower_bound(sposall + l, sposall + l + cntpos[ind], POS[ind]) -
                (sposall + l);
    int itneg = lower_bound(snegall + l, snegall + l + cntneg[ind], NEG[ind]) -
                (snegall + l);
    SUM[ind] = (M - itpos) * (long long)POS[ind] +
               (M - itneg) * (long long)NEG[ind] +
               (itpos ? ssposall[l + itpos - 1] : 0) +
               (itneg ? ssnegall[l + itneg - 1] : 0);
    if (DEBUG && ind == BAD)
      cerr << "last1: " << (M - itpos) * (long long)POS[ind] << ' '
           << (M - itneg) * (long long)NEG[ind] << ' '
           << (itpos ? ssposall[l + itpos - 1] : 0) << ' '
           << (itneg ? ssnegall[l + itneg - 1] : 0) << endl;
  } else if (POS[ind] < MAX) {
    int itpos =
        lower_bound(spos + l, spos + l + cnt[ind], POS[ind]) - (spos + l);
    assert(itpos <= cntneg[ind]);
    SUM[ind] = SUMNEG[ind] + (cntneg[ind] - itpos) * (long long)POS[ind] +
               (itpos ? sspos[l + itpos - 1] : 0);
    if (DEBUG && ind == BAD)
      cerr << "last2: " << SUMNEG[ind] << ' '
           << (cntneg[ind] - itpos) * (long long)POS[ind] << ' '
           << (itpos ? ssposall[l + itpos - 1] : 0) << endl;
  } else if (NEG[ind] < MAX) {
    int itneg =
        lower_bound(sneg + l, sneg + l + cnt[ind], NEG[ind]) - (sneg + l);
    assert(itneg <= cntpos[ind]);
    SUM[ind] = SUMPOS[ind] + (cntpos[ind] - itneg) * (long long)NEG[ind] +
               (itneg ? ssneg[l + itneg - 1] : 0);
    if (DEBUG && ind == BAD)
      cerr << "last3: " << SUMPOS[ind] << ' '
           << (cntpos[ind] - itneg) * (long long)NEG[ind] << ' '
           << (itneg ? ssneg[l + itneg - 1] : 0) << ' ' << cntpos[ind] << ' '
           << itneg << ' ' << ssneg[l] << endl;
  }
}
void update(int ind, int y) {
  int val = abs(y);
  int l = ind * M, r = ind * M + M;
  if (y > 0) {
    if (val >= POS[ind]) return;
    POS[ind] = val;
    int itpos = lower_bound(sposall + l, sposall + l + cntpos[ind], POS[ind]) -
                (sposall + l);
    SUMPOS[ind] = (M - itpos) * (long long)POS[ind] +
                  (itpos ? ssposall[l + itpos - 1] : 0);
    calcs(ind);
  } else {
    if (val >= NEG[ind]) return;
    NEG[ind] = val;
    int itneg = lower_bound(snegall + l, snegall + l + cntneg[ind], NEG[ind]) -
                (snegall + l);
    SUMNEG[ind] = (M - itneg) * (long long)NEG[ind] +
                  (itneg ? ssnegall[l + itneg - 1] : 0);
    calcs(ind);
  }
}
int main() {
  int T = 10000;
  if (!DEBUG) scanf("%d", &T);
  for (int i = 0; i < N / M; ++i) POS[i] = NEG[i] = MAX;
  for (int i = 0; i < N; ++i)
    stupidpos[i] = stupidneg[i] = pos[i] = neg[i] = MAX;
  for (int i = 0; i < N / M; ++i) {
    build(i);
  }
  const int LIM = 2 * M;
  for (int q = 0; q < T; ++q) {
    int type, l, r;
    if (!DEBUG)
      scanf("%d%d%d", &type, &l, &r);
    else {
      type = rand() % 2 + 1;
      r = rand() % S + 1;
      l = rand() % r;
    }
    --l;
    --r;
    int L = l / M * M, R = r / M * M;
    if (DEBUG) cerr << "test: " << q << endl;
    if (type == 1) {
      int y;
      if (!DEBUG)
        scanf("%d", &y);
      else
        y = (rand() % 1000 + 1) * (rand() % 2 * 2 - 1);
      if (DEBUG)
        for (int i = l; i < r; ++i) {
          if (y > 0)
            stupidpos[i] = min(stupidpos[i], y);
          else
            stupidneg[i] = min(stupidneg[i], -y);
        }
      if (r - l < LIM) {
        for (int i = l / M; i <= (r - 1) / M; ++i) push(i);
        for (int i = l; i < r; ++i) upd(i, y);
        for (int i = l / M; i <= (r - 1) / M; ++i) build(i);
      } else {
        push(l / M);
        push(r / M);
        for (int i = l; i < L + M; ++i) upd(i, y);
        for (int i = R; i < r; ++i) upd(i, y);
        build(l / M);
        build(r / M);
        for (int i = L / M + 1; i < R / M; ++i) {
          update(i, y);
        }
      }
    } else {
      long long res = 0;
      if (r - l < LIM) {
        for (int i = l / M; i <= (r - 1) / M; ++i) {
          push(i);
        }
        for (int i = l; i < r; ++i) {
          res += sum[i];
        }
      } else {
        push(l / M);
        push(r / M);
        for (int i = l; i < L + M; ++i) res += sum[i];
        for (int i = R; i < r; ++i) res += sum[i];
        for (int i = L / M + 1; i < R / M; ++i) {
          res += SUM[i];
          if (DEBUG) {
            cerr << "SUM: " << i << ' ' << SUMPOS[i] << ' ' << SUMNEG[i] << ' '
                 << SUM[i] << endl;
            for (int j = i * M; j < i * M + M; ++j)
              cerr << stupidpos[j] << ' ' << stupidneg[j] << ',';
            cerr << endl;
          }
        }
      }
      printf("%lld\n", res);
      if (DEBUG) {
        long long stupid = 0;
        for (int i = l; i < r; ++i)
          if (max(stupidpos[i], stupidneg[i]) < MAX)
            stupid += stupidpos[i] + stupidneg[i];
        cerr << l << ' ' << r << ' ' << res << ' ' << stupid << endl;
        assert(res == stupid);
      }
    }
  }
  return 0;
}
