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, N = 100000;
struct Segment_tree1 {
  int T[400010];
  void Build(int now, int l, int r) {
    T[now] = INF;
    if (l == r) return;
    int mid = l + r >> 1;
    Build(now << 1, l, mid), Build(now << 1 | 1, mid + 1, r);
  }
  void Update(int now, int l, int r, int L, int R, int x) {
    if (l == L && r == R) {
      T[now] = min(T[now], x);
      return;
    }
    int mid = l + r >> 1;
    if (R <= mid)
      Update(now << 1, l, mid, L, R, x);
    else if (L > mid)
      Update(now << 1 | 1, mid + 1, r, L, R, x);
    else
      Update(now << 1, l, mid, L, mid, x),
          Update(now << 1 | 1, mid + 1, r, mid + 1, R, x);
  }
  int Query(int now, int l, int r, int pos) {
    if (l == r) return T[now];
    int mid = l + r >> 1;
    if (pos <= mid) return min(T[now], Query(now << 1, l, mid, pos));
    return min(T[now], Query(now << 1 | 1, mid + 1, r, pos));
  }
} R[2];
struct Segment_tree2 {
  int mx1[400010], cnt[400010], mx2[400010];
  long long sum[400010];
  void pushup(int now) {
    mx1[now] = max(mx1[now << 1], mx1[now << 1 | 1]);
    cnt[now] = (mx1[now] == mx1[now << 1] ? cnt[now << 1] : 0) +
               (mx1[now] == mx1[now << 1 | 1] ? cnt[now << 1 | 1] : 0);
    mx2[now] = max(
        mx1[now] == mx1[now << 1] ? mx2[now << 1] : mx1[now << 1],
        mx1[now] == mx1[now << 1 | 1] ? mx2[now << 1 | 1] : mx1[now << 1 | 1]);
    sum[now] = sum[now << 1] + sum[now << 1 | 1];
  }
  void Build(int now, int l, int r) {
    if (l == r) {
      mx1[now] = 0, cnt[now] = 1, mx2[now] = -1, sum[now] = 0;
      return;
    }
    int mid = l + r >> 1;
    Build(now << 1, l, mid), Build(now << 1 | 1, mid + 1, r);
    pushup(now);
  }
  void pushdown(int now) {
    if (mx1[now << 1] > mx1[now]) {
      sum[now << 1] -= 1ll * (mx1[now << 1] - mx1[now]) * cnt[now << 1];
      mx1[now << 1] = mx1[now];
    }
    if (mx1[now << 1 | 1] > mx1[now]) {
      sum[now << 1 | 1] -=
          1ll * (mx1[now << 1 | 1] - mx1[now]) * cnt[now << 1 | 1];
      mx1[now << 1 | 1] = mx1[now];
    }
  }
  void Update(int now, int l, int r, int L, int R, int x) {
    if (l == L && r == R) {
      if (x >= mx1[now]) return;
      if (x > mx2[now]) {
        sum[now] -= 1ll * (mx1[now] - x) * cnt[now];
        mx1[now] = x;
        return;
      }
      pushdown(now);
      int mid = l + r >> 1;
      Update(now << 1, l, mid, l, mid, x),
          Update(now << 1 | 1, mid + 1, r, mid + 1, r, x);
      pushup(now);
      return;
    }
    pushdown(now);
    int mid = l + r >> 1;
    if (R <= mid)
      Update(now << 1, l, mid, L, R, x);
    else if (L > mid)
      Update(now << 1 | 1, mid + 1, r, L, R, x);
    else
      Update(now << 1, l, mid, L, mid, x),
          Update(now << 1 | 1, mid + 1, r, mid + 1, R, x);
    pushup(now);
  }
  void Modify(int now, int l, int r, int pos, int x) {
    if (l == r) {
      mx1[now] = x, cnt[now] = 1, mx2[now] = -1, sum[now] = x;
      return;
    }
    pushdown(now);
    int mid = l + r >> 1;
    if (pos <= mid)
      Modify(now << 1, l, mid, pos, x);
    else
      Modify(now << 1 | 1, mid + 1, r, pos, x);
    pushup(now);
  }
  long long Query(int now, int l, int r, int L, int R) {
    if (l == L && r == R) return sum[now];
    pushdown(now);
    int mid = l + r >> 1;
    if (R <= mid) return Query(now << 1, l, mid, L, R);
    if (L > mid) return Query(now << 1 | 1, mid + 1, r, L, R);
    return Query(now << 1, l, mid, L, mid) +
           Query(now << 1 | 1, mid + 1, r, mid + 1, R);
  }
} seg[2];
set<int> S[4];
int main() {
  R[0].Build(1, 1, N), R[1].Build(1, 1, N), seg[0].Build(1, 1, N),
      seg[1].Build(1, 1, N);
  for (int i = 1; i <= N; i++) S[3].insert(i);
  int q;
  scanf("%d", &q);
  while (q--) {
    int op, l, r, x;
    scanf("%d%d%d", &op, &l, &r), r--;
    if (op == 2)
      printf("%lld\n",
             seg[0].Query(1, 1, N, l, r) + seg[1].Query(1, 1, N, l, r));
    else {
      scanf("%d", &x);
      int d = 0;
      if (x < 0) x = -x, d = 1;
      seg[d].Update(1, 1, N, l, r, x), R[d].Update(1, 1, N, l, r, x);
      for (int i = 0; i < 4; i++) {
        if (i >> d & 1) {
          set<int>::iterator it = S[i].lower_bound(l);
          while (it != S[i].end() && *it <= r) {
            S[i ^ 1 << d].insert(*it);
            if ((i ^ 1 << d) == 0) {
              seg[0].Modify(1, 1, N, *it, R[0].Query(1, 1, N, *it));
              seg[1].Modify(1, 1, N, *it, R[1].Query(1, 1, N, *it));
            }
            it = S[i].erase(it);
          }
        }
      }
    }
  }
  return 0;
}
