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;
struct query {
  int t, l, r, k;
  void read() {
    cin >> t >> l >> r;
    assert(t == 1 || t == 2);
    if (t == 1) cin >> k;
  }
};
struct group {
  int c[2], cnt;
};
int pos_at(const vector<int> &v, int what) {
  int pos = lower_bound((v).begin(), (v).end(), what) - v.begin();
  assert(pos != (int)(v).size() && v[pos] == what);
  return pos;
}
void solve(int q) {
  const int n = (int)1e5;
  const int inf = (int)1e9 + 1;
  vector<query> qs(q);
  vector<int> pos;
  pos.push_back(1);
  pos.push_back(n);
  for (int i = 0; i < (int)(q); ++i) {
    qs[i].read();
    pos.push_back(qs[i].l);
    pos.push_back(qs[i].r);
  }
  sort((pos).begin(), (pos).end());
  pos.resize(unique((pos).begin(), (pos).end()) - pos.begin());
  vector<group> gr((int)(pos).size() - 1);
  for (int i = 0; i < (int)((int)(gr).size()); ++i) {
    for (int j = 0; j < (int)(2); ++j) gr[i].c[j] = inf;
    gr[i].cnt = pos[i + 1] - pos[i];
  }
  for (int i = 0; i < (int)(q); ++i) {
    int fl = pos_at(pos, qs[i].l);
    int fr = pos_at(pos, qs[i].r);
    if (qs[i].t == 1) {
      int side = (qs[i].k > 0 ? 0 : 1);
      int ny = abs(qs[i].k);
      for (int j = fl; j < fr; j++) gr[j].c[side] = min(gr[j].c[side], ny);
    } else {
      assert(qs[i].t == 2);
      long long ans = 0;
      for (int j = fl; j < fr; j++) {
        ans += ((gr[j].c[0] < inf && gr[j].c[1] < inf)
                    ? (long long)gr[j].cnt * (gr[j].c[0] + gr[j].c[1])
                    : 0);
      }
      cout << ans << "\n";
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  while (cin >> n) solve(n);
}
