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 + 5;
struct SegmentBeats {
  struct node {
    long long sum;
    int mx1, mx2, cnt, lz;
  } seg[N << 2];
  SegmentBeats() { build(); }
  inline node merge(node a, node b) {
    if (a.mx1 < b.mx1) swap(a, b);
    a.mx1 > b.mx1 ? a.mx2 = max(a.mx2, b.mx1) : a.cnt += b.cnt;
    a.sum += b.sum, a.lz = 0, a.mx2 = max(a.mx2, b.mx2);
    return a;
  }
  inline void change(int id, int x) {
    if (seg[id].mx1 > x) {
      seg[id].sum += 1LL * seg[id].cnt * (x - seg[id].mx1);
      seg[id].mx1 = seg[id].lz = x;
    }
  }
  inline void shift(int id) {
    if (seg[id].lz) {
      change(id << 1 | 1, seg[id].lz);
      change(id << 1, seg[id].lz);
      seg[id].lz = 0;
    }
  }
  void build(int id = 1, int st = 0, int en = N) {
    seg[id].cnt = en - st;
    if (en - st == 1) return;
    int mid = st + en >> 1;
    build(id << 1, st, mid);
    build(id << 1 | 1, mid, en);
  }
  void set(int p, int x, int id = 1, int st = 0, int en = N) {
    if (en - st == 1) {
      seg[id] = {x, x, 0, 1, 0};
      return;
    }
    shift(id);
    int mid = st + en >> 1;
    p < mid ? set(p, x, id << 1, st, mid) : set(p, x, id << 1 | 1, mid, en);
    seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
  }
  void update(int l, int r, int x, int id = 1, int st = 0, int en = N) {
    if (r <= st || en <= l || seg[id].mx1 <= x) return;
    if (l <= st && en <= r && seg[id].mx2 < x) return change(id, x);
    shift(id);
    int mid = st + en >> 1;
    update(l, r, x, id << 1, st, mid);
    update(l, r, x, id << 1 | 1, mid, en);
    seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
  }
  long long get(int l, int r, int id = 1, int st = 0, int en = N) {
    if (r <= st || en <= l) return 0;
    if (l <= st && en <= r) return seg[id].sum;
    shift(id);
    int mid = st + en >> 1;
    return get(l, r, id << 1, st, mid) + get(l, r, id << 1 | 1, mid, en);
  }
} A[2];
struct SegmentMin {
  int seg[N << 2];
  SegmentMin() { memset(seg, 63, sizeof seg); }
  void update(int l, int r, int x, int id = 1, int st = 0, int en = N) {
    if (r <= st || en <= l) return;
    if (l <= st && en <= r) {
      seg[id] = min(seg[id], x);
      return;
    }
    int mid = st + en >> 1;
    update(l, r, x, id << 1, st, mid);
    update(l, r, x, id << 1 | 1, mid, en);
  }
  int get(int p, int id = 1, int st = 0, int en = N) {
    if (en - st == 1) return seg[id];
    int mid = st + en >> 1;
    return min(seg[id], p < mid ? get(p, id << 1, st, mid)
                                : get(p, id << 1 | 1, mid, en));
  }
} B[2];
set<int> S[3];
int main() {
  int q;
  scanf("%d", &q);
  for (int i = 0; i < N; i++) S[2].insert(i);
  while (q--) {
    int t, l, r;
    scanf("%d%d%d", &t, &l, &r);
    if (t & 1) {
      int k;
      scanf("%d", &k);
      auto it = S[2].lower_bound(l);
      while (it != S[2].end() && *it < r) {
        S[k < 0].insert(*it), S[2].erase(it);
        it = S[2].lower_bound(l);
      }
      it = S[k > 0].lower_bound(l), B[k < 0].update(l, r, abs(k));
      while (it != S[k > 0].end() && *it < r) {
        A[k < 0].set(*it, B[k < 0].get(*it));
        A[k > 0].set(*it, B[k > 0].get(*it));
        S[k > 0].erase(it), it = S[k > 0].lower_bound(l);
      }
      A[k < 0].update(l, r, abs(k));
    } else
      printf("%lld\n", A[0].get(l, r) + A[1].get(l, r));
  }
}
