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>
const int lg = 17;
const int mxn = 1 << lg;
struct SegmentTree {
  int tagmx[mxn << 1], tag[mxn << 1];
  long long sum[mxn << 1];
  int sz[mxn << 1], mx[mxn << 1], mxcnt[mxn << 1], se[mxn << 1];
  SegmentTree() {
    memset(tagmx, 0, sizeof(tagmx));
    memset(tag, 0, sizeof(tag));
    memset(sum, 0, sizeof(sum));
    memset(sz, 0, sizeof(sz));
    memset(mx, 0, sizeof(mx));
    memset(mxcnt, 0, sizeof(mxcnt));
    memset(se, 0, sizeof(se));
  }
  void push(int x, int vmx, int v) {
    tagmx[x] += vmx;
    tag[x] += v;
    sum[x] += 1LL * sz[x] * v + 1LL * mxcnt[x] * vmx;
    mx[x] += v + vmx;
    se[x] += v;
  }
  void pushdown(int x) {
    if (tagmx[x] || tag[x]) {
      push(x << 1, mx[x << 1] + tagmx[x] + tag[x] == mx[x] ? tagmx[x] : 0,
           tag[x]);
      push(x << 1 | 1,
           mx[x << 1 | 1] + tagmx[x] + tag[x] == mx[x] ? tagmx[x] : 0, tag[x]);
      tagmx[x] = tag[x] = 0;
    }
  }
  void pushup(int x) {
    sz[x] = sz[x << 1] + sz[x << 1 | 1];
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
    mx[x] = std::max(mx[x << 1], mx[x << 1 | 1]);
    mxcnt[x] = 0;
    if (mx[x << 1] == mx[x]) mxcnt[x] += mxcnt[x << 1];
    if (mx[x << 1 | 1] == mx[x]) mxcnt[x] += mxcnt[x << 1 | 1];
    se[x] = std::max(se[x << 1], se[x << 1 | 1]);
    if (mx[x << 1] < mx[x]) se[x] = std::max(se[x], mx[x << 1]);
    if (mx[x << 1 | 1] < mx[x]) se[x] = std::max(se[x], mx[x << 1 | 1]);
  }
  void enable(int x, int v) {
    x += mxn;
    for (int i = lg; i; --i) pushdown(x >> i);
    sz[x] = 1;
    mxcnt[x] = 1;
    mx[x] = v;
    sum[x] = v;
    se[x] = 0;
    for (int i = 1; i <= lg; ++i) pushup(x >> i);
  }
  int get(int x) {
    x += mxn;
    for (int i = lg; i; --i) pushdown(x >> i);
    return sum[x];
  }
  void update(int l, int r, int v, int i = 1, int a = 0, int b = mxn) {
    if (l <= a && b <= r) {
      if (v > mx[i]) return;
      if (v > se[i]) return push(i, v - mx[i], 0);
    }
    if (r <= a || b <= l) return;
    pushdown(i);
    int m = (a + b) >> 1;
    update(l, r, v, i << 1, a, m);
    update(l, r, v, i << 1 | 1, m, b);
    pushup(i);
  }
  long long query(int l, int r, int i = 1, int a = 0, int b = mxn) {
    if (l <= a && b <= r) return sum[i];
    if (r <= a || b <= l) return 0;
    pushdown(i);
    int m = (a + b) >> 1;
    return query(l, r, i << 1, a, m) + query(l, r, i << 1 | 1, m, b);
  }
} segu, segd, seguans, segdans;
std::set<int> setu, setd;
int flg[mxn];
void qwq(int x) {
  ++flg[x];
  if (flg[x] == 2) {
    seguans.enable(x, segu.get(x));
    segdans.enable(x, segd.get(x));
  }
}
void doit(std::set<int> &st, int l, int r) {
  std::set<int>::iterator it = st.lower_bound(l);
  while (it != st.end() && *it < r) {
    qwq(*it);
    it = st.erase(it);
  }
}
int main() {
  for (int i = 0; i < (int)(mxn); ++i) {
    setu.insert(i);
    setd.insert(i);
    segu.enable(i, 0x3f3f3f3f);
    segd.enable(i, 0x3f3f3f3f);
  }
  int q;
  scanf("%d", &q);
  while (q--) {
    int tp;
    scanf("%d", &tp);
    if (tp == 1) {
      int l, r, k;
      scanf("%d %d %d", &l, &r, &k);
      (k > 0 ? segu : segd).update(l, r, k > 0 ? k : -k);
      doit(k > 0 ? setu : setd, l, r);
      (k > 0 ? seguans : segdans).update(l, r, k > 0 ? k : -k);
    } else {
      int l, r;
      scanf("%d %d", &l, &r);
      printf("%lld\n", seguans.query(l, r) + segdans.query(l, r));
    }
  }
  return 0;
}
