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 + 10;
const int inf = 1e9 + 10;
int n, m, x, y, v, opt;
struct segment_tree_beats {
  int a[N], tot, rt;
  struct tree {
    int l, r, mx, nmx, mx_, tag;
    long long s;
    bool f;
  } t[N << 1];
  void pushup(int k) {
    if (t[t[k].l].mx == t[t[k].r].mx) {
      t[k].mx = t[t[k].l].mx;
      t[k].nmx = t[t[k].l].nmx + t[t[k].r].nmx;
      t[k].mx_ = max(t[t[k].l].mx_, t[t[k].r].mx_);
    }
    if (t[t[k].l].mx > t[t[k].r].mx) {
      t[k].mx = t[t[k].l].mx;
      t[k].nmx = t[t[k].l].nmx;
      t[k].mx_ = max(t[t[k].l].mx_, t[t[k].r].mx);
    }
    if (t[t[k].r].mx > t[t[k].l].mx) {
      t[k].mx = t[t[k].r].mx;
      t[k].nmx = t[t[k].r].nmx;
      t[k].mx_ = max(t[t[k].r].mx_, t[t[k].l].mx);
    }
    t[k].s = t[t[k].l].s + t[t[k].r].s;
    t[k].f = t[t[k].l].f & t[t[k].r].f;
  }
  void tag_(int k, int v) {
    if (t[k].mx <= v) return;
    t[k].s -= 1ll * t[k].nmx * (t[k].mx - v);
    t[k].mx = v;
    t[k].tag = v;
    t[k].f = 1;
  }
  void pushdown(int k) {
    if (t[k].tag) tag_(t[k].l, t[k].tag), tag_(t[k].r, t[k].tag), t[k].tag = 0;
  }
  void update(int l, int r, int k, int x, int y, int v) {
    pushdown(k);
    int mid = (l + r) >> 1;
    if (x <= l && r <= y) {
      if (v > t[k].mx_) {
        tag_(k, v);
        return;
      }
      update(l, mid, t[k].l, x, y, v);
      update(mid + 1, r, t[k].r, x, y, v);
    }
    if (x <= mid) update(l, mid, t[k].l, x, y, v);
    if (mid < y) update(mid + 1, r, t[k].r, x, y, v);
    pushup(k);
  }
  void update(int x, int y, int v) { update(1, n, rt, x, y, v); }
  void init(int l, int r, int &k) {
    if (!k) k = ++tot;
    if (l == r) {
      t[k].mx = inf;
      t[k].mx_ = 0;
      t[k].nmx = 1;
      t[k].s = inf;
      return;
    }
    int mid = (l + r) >> 1;
    init(l, mid, t[k].l);
    init(mid + 1, r, t[k].r);
    pushup(k);
  }
  void init() { init(1, n, rt); }
} t1, t2;
long long inquiry(int l, int r, int k1, int k2, int x, int y) {
  t1.pushdown(k1), t2.pushdown(k2);
  if (x <= l && r <= y) {
    if (t1.t[k1].f && t2.t[k2].f) return t1.t[k1].s + t2.t[k2].s;
  }
  if (t1.t[k1].s % inf == 0 || t2.t[k2].s % inf == 0) return 0;
  if (l == r) return 0;
  int mid = (l + r) >> 1;
  long long res = 0;
  if (x <= mid) res += inquiry(l, mid, t1.t[k1].l, t2.t[k2].l, x, y);
  if (mid < y) res += inquiry(mid + 1, r, t1.t[k1].r, t2.t[k2].r, x, y);
  return res;
}
long long inquiry(int x, int y) { return inquiry(1, n, t1.rt, t2.rt, x, y); }
int main() {
  n = 1e5;
  scanf("%d", &m);
  t1.init(), t2.init();
  while (m--) {
    scanf("%d%d%d", &opt, &x, &y);
    y--;
    if (opt == 1) {
      scanf("%d", &v);
      if (v > 0)
        t1.update(x, y, v);
      else
        t2.update(x, y, -v);
    }
    if (opt == 2) printf("%lld\n", inquiry(x, y));
  }
}
