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 MAXN = 2000007;
const int N = MAXN;
const int TWO = 2;
const long long INF = 1e9 + 7;
struct Node {
  long long max, nummax, nextmax, push, sum;
  Node() : max(INF), nummax(0), nextmax(0), push(0), sum(0) {}
};
Node tree[TWO][MAXN];
void init(int v, int l, int r) {
  if (r < l) return;
  tree[0][v].max = tree[1][v].max = INF;
  tree[0][v].nextmax = tree[1][v].nextmax = 0;
  tree[0][v].sum = tree[1][v].sum = (long long)(r - l + 1) * INF;
  tree[0][v].nummax = tree[1][v].nummax = r - l + 1;
  tree[0][v].push = tree[1][v].push = 0;
  if (l == r) return;
  int mid = (r + l) / 2;
  init(2 * v, l, mid);
  init(2 * v + 1, mid + 1, r);
}
void upd(int num, int v, int l, int r) {
  tree[num][v].sum = tree[num][2 * v].sum + tree[num][2 * v + 1].sum;
  tree[num][v].max = max(tree[num][2 * v].max, tree[num][2 * v + 1].max);
  if (tree[num][2 * v].max == tree[num][2 * v + 1].max) {
    tree[num][v].nummax = tree[num][2 * v].nummax + tree[num][2 * v + 1].nummax;
    tree[num][v].nextmax =
        max(tree[num][2 * v].nextmax, tree[num][2 * v + 1].nextmax);
  } else if (tree[num][2 * v].max > tree[num][2 * v + 1].max) {
    tree[num][v].nextmax =
        max(tree[num][2 * v].nextmax, tree[num][2 * v + 1].max);
    tree[num][v].nummax = tree[num][2 * v].nummax;
  } else {
    tree[num][v].nextmax =
        max(tree[num][2 * v + 1].nextmax, tree[num][2 * v].max);
    tree[num][v].nummax = tree[num][2 * v + 1].nummax;
  }
}
void push1(int num, int v, int l, int r);
void take(int num, int v, int l, int r, int k) {
  if (r < l || tree[num][v].max <= k) return;
  if (tree[num][v].nextmax < k) {
    tree[num][v].sum += (long long)(k - tree[num][v].max) * tree[num][v].nummax;
    tree[num][v].max = k;
    tree[num][v].push = k;
    return;
  }
  int mid = (r + l) / 2;
  push1(num, 2 * v, l, mid);
  push1(num, 2 * v + 1, mid + 1, r);
  upd(num, v, l, r);
}
void push1(int num, int v, int l, int r) {
  if (r < l || tree[num][v].push == 0) return;
  int mid = (r + l) / 2;
  take(num, 2 * v, l, mid, tree[num][v].push);
  take(num, 2 * v + 1, mid + 1, r, tree[num][v].push);
  tree[num][v].push = 0;
}
void tu(int num, int v, int l, int r, int ql, int qr, int k) {
  push1(num, v, l, r);
  if (r < l || qr < l || r < ql || k >= tree[num][v].max) return;
  if (ql <= l && r <= qr && k > tree[num][v].nextmax) {
    take(num, v, l, r, k);
    return;
  }
  int mid = (r + l) / 2;
  tu(num, 2 * v, l, mid, ql, qr, k);
  tu(num, 2 * v + 1, mid + 1, r, ql, qr, k);
  upd(num, v, l, r);
}
long long tf(int v, int l, int r, int ql, int qr) {
  push1(0, v, l, r);
  push1(1, v, l, r);
  if (r < l || ql > r || l > qr ||
      INF * (long long)(r - l + 1) == max(tree[0][v].sum, tree[1][v].sum))
    return 0;
  if (ql <= l && r <= qr && tree[0][v].max != INF && tree[1][v].max != INF) {
    return tree[0][v].sum + tree[1][v].sum;
  }
  if (r == l) return 0;
  int mid = (r + l) / 2;
  long long ans = tf(2 * v, l, mid, ql, qr) + tf(2 * v + 1, mid + 1, r, ql, qr);
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  string s;
  int q;
  cin >> q;
  int n = 100000;
  init(1, 1, n);
  for (int i = 0; i < q; i++) {
    int x, l, r;
    cin >> x >> l >> r;
    r--;
    if (x == 1) {
      int k;
      cin >> k;
      if (k > 0)
        tu(0, 1, 1, n, l, r, k);
      else
        tu(1, 1, 1, n, l, r, -k);
    } else
      cout << tf(1, 1, n, l, r) << "\n";
  }
  return 0;
}
