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 = 4e5 + 5, inf = 2e9;
int n = 1e5, Q, mn[N][2], sm[N][2], cnt[N][2], tag[N][2], v[N];
long long sum[N];
void modify(int i, int x, int l, int r, int nl, int nr, int k);
void down(int x, int l, int r) {
  for (int i = 0; i < 2; i++)
    if (tag[x][i] != inf) {
      modify(i, x << 1, l, ((l + r) >> 1), l, ((l + r) >> 1), tag[x][i]);
      modify(i, x << 1 | 1, ((l + r) >> 1) + 1, r, ((l + r) >> 1) + 1, r,
             tag[x][i]);
      tag[x][i] = inf;
    }
}
void up(int x) {
  sum[x] = sum[x << 1] + sum[x << 1 | 1];
  v[x] = v[x << 1] & v[x << 1 | 1];
  for (int i = 0; i < 2; i++) {
    mn[x][i] = max(mn[x << 1][i], mn[x << 1 | 1][i]);
    sm[x][i] = max(
        mn[x << 1][i] == mn[x][i] ? sm[x << 1][i] : mn[x << 1][i],
        mn[x << 1 | 1][i] == mn[x][i] ? sm[x << 1 | 1][i] : mn[x << 1 | 1][i]);
    cnt[x][i] = (mn[x << 1][i] == mn[x][i] ? cnt[x << 1][i] : 0) +
                (mn[x << 1 | 1][i] == mn[x][i] ? cnt[x << 1 | 1][i] : 0);
  }
}
void modify(int i, int x, int l, int r, int nl, int nr, int k) {
  if (l == r) {
    v[x] |= 1 << i;
    mn[x][i] = min(mn[x][i], k);
    if (v[x] == 3) cnt[x][0] = cnt[x][1] = 1, sum[x] = mn[x][0] + mn[x][1];
    return;
  }
  if (nl <= l && r <= nr && (v[x] & (1 << i))) {
    if (k >= mn[x][i]) return;
    if (k > sm[x][i]) {
      sum[x] -= 1ll * cnt[x][i] * (mn[x][i] - k), mn[x][i] = tag[x][i] = k;
      return;
    }
  }
  down(x, l, r);
  if (nl <= ((l + r) >> 1)) modify(i, x << 1, l, ((l + r) >> 1), nl, nr, k);
  if (nr > ((l + r) >> 1))
    modify(i, x << 1 | 1, ((l + r) >> 1) + 1, r, nl, nr, k);
  up(x);
}
long long Qsum(int x, int l, int r, int nl, int nr) {
  if (nl <= l && r <= nr) return sum[x];
  down(x, l, r);
  long long res = 0;
  if (nl <= ((l + r) >> 1)) res += Qsum(x << 1, l, ((l + r) >> 1), nl, nr);
  if (nr > ((l + r) >> 1))
    res += Qsum(x << 1 | 1, ((l + r) >> 1) + 1, r, nl, nr);
  return res;
}
int main() {
  scanf("%d", &Q);
  for (int i = 0; i < N; i++)
    for (int j = 0; j < 2; j++) mn[i][j] = tag[i][j] = inf;
  while (Q--) {
    int t, l, r, x;
    scanf("%d%d%d", &t, &l, &r), r--;
    if (t & 1)
      scanf("%d", &x),
          x > 0 ? modify(0, 1, 1, n, l, r, x) : modify(1, 1, 1, n, l, r, -x);
    else
      printf("%lld\n", Qsum(1, 1, n, l, r));
  }
  return 0;
}
