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 N = 1e5;
const int INF = 1e9 + 5;
const int BUCKET = 333;
vector<int> bucket[2][BUCKET];
vector<long long> sum[2][BUCKET];
int mins[2][BUCKET];
int val[2][N + 5];
bool udah[N + 5];
set<int> active[2];
int q;
void update_bucket(int id) {
  for (int i = 0; i < 2; i++) {
    bucket[i][id].clear();
    sum[i][id].clear();
    int atas = min(id * BUCKET + BUCKET - 1, N - 1);
    for (int j = id * BUCKET; j <= atas; j++) {
      if (udah[j]) bucket[i][id].push_back(min(mins[i][id], val[i][j]));
    }
    sort(bucket[i][id].begin(), bucket[i][id].end());
    for (int x : bucket[i][id]) {
      long long cur = x;
      if (!sum[i][id].empty()) cur += sum[i][id].back();
      sum[i][id].push_back(cur);
    }
  }
}
void add_to_bucket(int pos) {
  int id = pos / BUCKET;
  update_bucket(id);
}
void update(int l, int r, int vals) {
  int tipe = 0;
  if (vals < 0) {
    vals = -vals;
    tipe = 1;
  }
  int i = l;
  int nex = i / BUCKET * BUCKET + BUCKET - 1;
  nex = min(nex, r);
  while (i <= nex) {
    val[tipe][i] = min(val[tipe][i], vals);
    i++;
  }
  update_bucket(l / BUCKET);
  if (nex < r) {
    int pos = i / BUCKET;
    while (pos * BUCKET + BUCKET - 1 < r) {
      mins[tipe][pos] = min(mins[tipe][pos], vals);
      i += BUCKET;
      pos++;
    }
    while (i <= r) {
      val[tipe][i] = min(val[tipe][i], vals);
      i++;
    }
    update_bucket(r / BUCKET);
  }
  while (1) {
    auto it = active[tipe].lower_bound(l);
    if (it == active[tipe].end() || *it > r) {
      break;
    }
    int pos = *it;
    if (!udah[pos] && !active[tipe ^ 1].count(pos)) {
      udah[pos] = true;
      add_to_bucket(pos);
    }
    active[tipe].erase(pos);
  }
}
long long query(int l, int r) {
  int i = l;
  int nex = i / BUCKET * BUCKET + BUCKET - 1;
  nex = min(nex, r);
  long long ret = 0;
  int buck = i / BUCKET;
  while (i <= nex) {
    if (udah[i]) {
      int atas = min(val[0][i], mins[0][buck]);
      int bawah = min(val[1][i], mins[1][buck]);
      ret += atas;
      ret += bawah;
    }
    i++;
  }
  if (nex < r) {
    int pos = i / BUCKET;
    while (pos * BUCKET + BUCKET - 1 < r) {
      if (!bucket[0][pos].empty()) {
        vector<int> &v = bucket[0][pos];
        int lb = lower_bound(v.begin(), v.end(), mins[0][pos]) - v.begin();
        if (lb > 0) {
          ret += sum[0][pos][lb - 1];
        }
        ret += 1ll * mins[0][pos] * (v.size() - lb);
        vector<int> &y = bucket[1][pos];
        lb = lower_bound(y.begin(), y.end(), mins[1][pos]) - y.begin();
        if (lb > 0) {
          ret += sum[1][pos][lb - 1];
        }
        ret += 1ll * mins[1][pos] * (y.size() - lb);
      }
      i += BUCKET;
      pos++;
    }
    buck = i / BUCKET;
    while (i <= r) {
      if (udah[i]) {
        ret += min(val[0][i], mins[0][buck]);
        ret += min(val[1][i], mins[1][buck]);
      }
      i++;
    }
  }
  return ret;
}
void init() {
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < N; j++) {
      active[i].insert(j);
      int idx = j / BUCKET;
      mins[0][idx] = INF;
      mins[1][idx] = INF;
      val[0][j] = INF;
      val[1][j] = INF;
    }
}
int main() {
  init();
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int tipe;
    scanf("%d", &tipe);
    if (tipe == 1) {
      int l, r, k;
      scanf("%d %d %d", &l, &r, &k);
      l--;
      r -= 2;
      update(l, r, k);
    } else {
      int l, r;
      scanf("%d %d", &l, &r);
      l--;
      r -= 2;
      printf("%lld\n", query(l, r));
    }
  }
  return 0;
}
