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 Inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
const int maxn = 1 << 17;
struct Segbeats {
  int mx[maxn << 1], nx[maxn << 1], mxs[maxn << 1];
  long long sm[maxn << 1];
  void inline init() { memset(mx, Inf, sizeof(mx)); }
  void inline push(int now, int x) {
    sm[now] -= 1ll * (mx[now] - x) * mxs[now];
    mx[now] = x;
  }
  void inline pd(int now) {
    if (mx[now] < mx[now << 1]) push(now << 1, mx[now]);
    if (mx[now] < mx[now << 1 | 1]) push(now << 1 | 1, mx[now]);
  }
  void inline pu(int now) {
    sm[now] = sm[now << 1] + sm[now << 1 | 1];
    if (mx[now << 1] > mx[now << 1 | 1]) {
      mx[now] = mx[now << 1];
      nx[now] = max(nx[now << 1], mx[now << 1 | 1]);
      mxs[now] = mxs[now << 1];
    } else if (mx[now << 1 | 1] > mx[now << 1]) {
      mx[now] = mx[now << 1 | 1];
      nx[now] = max(nx[now << 1 | 1], mx[now << 1]);
      mxs[now] = mxs[now << 1 | 1];
    } else {
      mx[now] = mx[now << 1];
      nx[now] = max(nx[now << 1], nx[now << 1 | 1]);
      mxs[now] = mxs[now << 1] + mxs[now << 1 | 1];
    }
  }
  void inline chmin(int l, int r, int x, int now = 1, int nl = 0,
                    int nr = maxn - 1) {
    if (nl >= l && nr <= r) {
      if (mx[now] < x) return;
      if (nx[now] < x) return push(now, x);
    }
    if (nl > r || nr < l) return;
    pd(now);
    int m = (nl + nr) >> 1;
    chmin(l, r, x, now << 1, nl, m);
    chmin(l, r, x, now << 1 | 1, m + 1, nr);
    pu(now);
  }
  long long inline query(int l, int r, int now = 1, int nl = 0,
                         int nr = maxn - 1) {
    if (nl >= l && nr <= r) return sm[now];
    if (nl > r || nr < l) return 0;
    pd(now);
    int m = (nl + nr) >> 1;
    return query(l, r, now << 1, nl, m) + query(l, r, now << 1 | 1, m + 1, nr);
  }
  void inline activate(int to, int now = 1, int nl = 0, int nr = maxn - 1) {
    if (nl == nr) return (void)(mxs[now] = 1, sm[now] = mx[now]);
    pd(now);
    int m = (nl + nr) >> 1;
    if (m >= to)
      activate(to, now << 1, nl, m);
    else
      activate(to, now << 1 | 1, m + 1, nr);
    pu(now);
  }
} sgz, sgf;
set<int> un[4];
void inline moveto(int l, int r, int fr, int to) {
  auto it = un[fr].lower_bound(l);
  while (it != un[fr].end() && *it <= r) {
    if (!to) sgf.activate(*it), sgz.activate(*it);
    un[to].insert(*it);
    it = un[fr].erase(it);
  }
}
int main() {
  int q;
  scanf("%d", &q);
  for (int i = 0; i < (maxn); ++i) un[3].insert(i);
  sgz.init();
  sgf.init();
  while (q--) {
    int mode;
    scanf("%d", &mode);
    if (mode == 1) {
      int l, r, k;
      scanf("%d%d%d", &l, &r, &k);
      --r;
      int sb = 0;
      if (k < 0) k = -k, sb = 1;
      if (sb) {
        sgf.chmin(l, r, k);
        moveto(l, r, 3, 1);
        moveto(l, r, 2, 0);
      } else {
        sgz.chmin(l, r, k);
        moveto(l, r, 3, 2);
        moveto(l, r, 1, 0);
      }
    } else {
      int l, r;
      scanf("%d%d", &l, &r);
      --r;
      printf("%lld\n", sgz.query(l, r) + sgf.query(l, r));
    }
  }
  return 0;
}
