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;
inline int read() {
  int s = 0, t = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') t = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
  return s * t;
}
const int N = 1e5 + 5;
const int Lim = 1e5;
long long s[N << 2];
struct Node {
  int p0, p1, t;
  void Init(int x) { p1 = x, p0 = 0; }
  friend Node operator+(Node A, Node B) {
    if (A.p1 < B.p1) swap(A, B);
    if (A.p1 == B.p1)
      A.t += B.t, A.p0 = max(A.p0, B.p0);
    else
      A.p0 = max(A.p0, B.p1);
    return A;
  }
};
struct Segment_Tree {
  Node tr[N << 2];
  int d[N << 2], h[N << 2];
  void Init(int x, int t) {
    tr[x].p1 += t, s[x] += 1ll * tr[x].t * t, d[x] += t;
  }
  void Pushup(int x) {
    tr[x] = tr[x << 1] + tr[x << 1 | 1], h[x] = h[x << 1] & h[x << 1 | 1];
  }
  void Pushdown(int x) {
    if (!d[x]) return;
    if (tr[x].p1 < tr[x << 1].p1) Init(x << 1, d[x]);
    if (tr[x].p1 < tr[x << 1 | 1].p1) Init(x << 1 | 1, d[x]);
    d[x] = 0;
  }
} F[2];
void Ins(int x, int l, int r, int ql, int qr, int t, int v) {
  if (ql <= l && r <= qr && F[t].h[x] && v > F[t].tr[x].p0) {
    int tp = F[t].tr[x].p1;
    return F[t].Init(x, min(0, v - tp));
  }
  if (l == r) {
    F[t].tr[x].p1 = v, F[t].h[x] = 1;
    if (F[t ^ 1].h[x]) {
      s[x] = v + F[t ^ 1].tr[x].p1;
      F[0].tr[x].t = F[1].tr[x].t = 1;
    }
    return;
  }
  int mid = (l + r) >> 1;
  F[0].Pushdown(x), F[1].Pushdown(x);
  if (ql <= mid) Ins(x << 1, l, mid, ql, qr, t, v);
  if (qr > mid) Ins(x << 1 | 1, mid + 1, r, ql, qr, t, v);
  F[0].Pushup(x), F[1].Pushup(x), s[x] = s[x << 1] + s[x << 1 | 1];
}
long long Ask(int x, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return s[x];
  int mid = (l + r) >> 1;
  long long res = 0;
  F[0].Pushdown(x), F[1].Pushdown(x);
  if (ql <= mid) res += Ask(x << 1, l, mid, ql, qr);
  if (qr > mid) res += Ask(x << 1 | 1, mid + 1, r, ql, qr);
  return res;
}
int main() {
  for (int T = read(); T; T--) {
    int op = read(), l = read(), r = read() - 1, x = 0;
    if (op == 1)
      x = read(), Ins(1, 1, Lim, l, r, (x > 0), abs(x));
    else
      printf("%lld\n", Ask(1, 1, Lim, l, r));
  }
  return 0;
}
