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 MaxX = 1e5;
const int MaxN = 2e5 + 15;
const int MaxK = 300;
const int INF = 1e9 + 1e8;
int q;
int upper[MaxN], lower[MaxN];
long long ans[MaxN];
map<int, int> low[MaxN], up[MaxN];
map<int, int> notUp[MaxN], notLow[MaxN];
int notBoth[MaxN];
int minUp[MaxN], minDown[MaxN];
void upPosUp(int pos, int val) {
  int k = pos / MaxK;
  if (upper[k] > val && minUp[pos] > val) {
    if (upper[k] == INF && lower[k] == INF && minUp[pos] == INF &&
        minDown[pos] == INF) {
      --notBoth[k];
      ++notLow[k][val];
    } else if (upper[k] == INF && minUp[pos] == INF) {
      int temp = min(lower[k], minDown[pos]);
      ans[k] += val + temp;
      --notUp[k][temp];
      if (notUp[k][temp] == 0) notUp[k].erase(temp);
      ++low[k][temp];
      ++up[k][val];
    } else if (lower[k] == INF && minDown[pos] == INF) {
      int temp = min(upper[k], minUp[pos]);
      --notLow[k][temp];
      if (notLow[k][temp] == 0) notLow[k].erase(temp);
      ++notLow[k][val];
    } else {
      ans[k] += val - min(upper[k], minUp[pos]);
      --up[k][min(upper[k], minUp[pos])];
      ++up[k][val];
    }
    minUp[pos] = val;
  }
}
void fullUp(int k, int val) {
  if (upper[k] > val) {
    for (map<int, int>::iterator it = notUp[k].begin(); it != notUp[k].end();
         ++it) {
      ans[k] += (val + it->first) * 1ll * it->second;
      low[k][it->first] += (it->second);
      up[k][val] += (it->second);
    }
    notUp[k].clear();
    map<int, int>::iterator it = notLow[k].upper_bound(val);
    int cnt = 0;
    long long sum = 0;
    for (; it != notLow[k].end(); ++it) cnt += it->second;
    it = notLow[k].upper_bound(val);
    notLow[k].erase(it, notLow[k].end());
    notLow[k][val] += cnt + notBoth[k];
    notBoth[k] = 0;
    cnt = 0;
    for (it = up[k].upper_bound(val); it != up[k].end(); ++it) {
      cnt += it->second;
      sum += it->second * 1ll * it->first;
    }
    it = up[k].upper_bound(val);
    up[k].erase(it, up[k].end());
    up[k][val] += cnt;
    ans[k] += cnt * 1ll * val - sum;
    upper[k] = val;
  }
}
void upUp(int l, int r, int val) {
  int L = l / MaxK;
  int R = r / MaxK;
  if (L == R) {
    for (int i = l; i <= r; ++i) upPosUp(i, val);
  } else {
    for (int i = l; i < (L + 1) * MaxK; ++i) upPosUp(i, val);
    ++L;
    while (L < R) {
      fullUp(L, val);
      ++L;
    }
    for (int i = L * MaxK; i <= r; ++i) upPosUp(i, val);
  }
}
void upPosDown(int pos, int val) {
  int k = pos / MaxK;
  if (lower[k] > val && minDown[pos] > val) {
    if (lower[k] == INF && minDown[pos] == INF && upper[k] == INF &&
        minUp[pos] == INF) {
      --notBoth[k];
      ++notUp[k][val];
    } else if (lower[k] == INF && minDown[pos] == INF) {
      int temp = min(upper[k], minUp[pos]);
      --notLow[k][temp];
      if (notLow[k][temp] == 0) notLow[k].erase(temp);
      ++up[k][temp];
      ++low[k][val];
      ans[k] += val + temp;
    } else if (upper[k] == INF && minUp[pos] == INF) {
      int temp = min(lower[k], minDown[pos]);
      --notUp[k][temp];
      if (notUp[k][temp] == 0) notUp[k].erase(temp);
      ++notUp[k][val];
    } else {
      int temp = min(lower[k], minDown[pos]);
      ans[k] += val - temp;
      --low[k][temp];
      ++low[k][val];
    }
    minDown[pos] = val;
  }
}
void fullDown(int k, int val) {
  if (lower[k] > val) {
    for (map<int, int>::iterator it = notLow[k].begin(); it != notLow[k].end();
         ++it) {
      ans[k] += (it->first + val) * 1ll * it->second;
      up[k][it->first] += it->second;
      low[k][val] += it->second;
    }
    notLow[k].clear();
    map<int, int>::iterator it;
    int cnt = 0;
    for (it = notUp[k].upper_bound(val); it != notUp[k].end(); ++it)
      cnt += it->second;
    it = notUp[k].upper_bound(val);
    notUp[k].erase(it, notUp[k].end());
    notUp[k][val] += cnt + notBoth[k];
    notBoth[k] = 0;
    cnt = 0;
    long long sum = 0;
    for (it = low[k].upper_bound(val); it != low[k].end(); ++it) {
      cnt += it->second;
      sum += it->first * 1ll * it->second;
    }
    it = low[k].upper_bound(val);
    low[k].erase(it, low[k].end());
    low[k][val] += cnt;
    ans[k] += cnt * 1ll * val - sum;
    lower[k] = val;
  }
}
void upDown(int l, int r, int val) {
  int L = l / MaxK;
  int R = r / MaxK;
  if (L == R) {
    for (int i = l; i <= r; ++i) upPosDown(i, val);
  } else {
    for (int i = l; i < (L + 1) * MaxK; ++i) upPosDown(i, val);
    ++L;
    while (L < R) {
      fullDown(L, val);
      ++L;
    }
    for (int i = L * MaxK; i <= r; ++i) upPosDown(i, val);
  }
}
int getPos(int pos) {
  int k = pos / MaxK;
  if (minUp[pos] < INF || upper[k] < INF)
    if (minDown[pos] < INF || lower[k] < INF)
      return min(minUp[pos], upper[k]) + min(minDown[pos], lower[k]);
  return 0;
}
long long get(int l, int r) {
  int L = l / MaxK;
  int R = r / MaxK;
  long long res = 0;
  if (L == R) {
    for (int i = l; i <= r; ++i) res += getPos(i);
  } else {
    for (int i = l; i < (L + 1) * MaxK; ++i) res += getPos(i);
    ++L;
    while (L < R) {
      res += ans[L];
      ++L;
    }
    for (int i = L * MaxK; i <= r; ++i) res += getPos(i);
  }
  return res;
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  srand(time(NULL));
  for (int i = 0; i * MaxK <= MaxX; ++i) {
    upper[i] = lower[i] = INF;
    ans[i] = 0;
    notBoth[i] = MaxK;
    for (int j = i * MaxK; j < (i + 1) * MaxK; ++j) minUp[j] = minDown[j] = INF;
  }
  int q;
  cin >> q;
  while (q-- > 0) {
    int t;
    cin >> t;
    if (t == 2) {
      int l, r;
      cin >> l >> r;
      --l;
      --r, --r;
      cout << get(l, r) << '\n';
    } else {
      int l, r, x;
      cin >> l >> r >> x;
      --l;
      r -= 2;
      if (x > 0)
        upUp(l, r, x);
      else
        upDown(l, r, -x);
    }
  }
}
