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;
void Freopen() {
  freopen(
      "title"
      ".in",
      "r", stdin);
  freopen(
      "title"
      ".out",
      "w", stdout);
}
int read() {
  int g = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || '9' < ch) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while ('0' <= ch && ch <= '9') {
    g = g * 10 + ch - '0';
    ch = getchar();
  }
  return g * f;
}
const int N = 1e5 + 5;
const int INF = 1e9 + 1;
struct Seg {
  int tag[N << 2], mx[N << 2], cx[N << 2], size[N << 2], ok[N << 2];
  long long su[N << 2];
  void updata(int v, int w) {
    su[v] -= 1ll * ok[v] * size[v] * mx[v];
    tag[v] = min(tag[v], w);
    mx[v] = min(mx[v], w);
    su[v] += 1ll * (ok[v] = 1) * size[v] * mx[v];
  }
  void down(int v) {
    if (!(tag[v] ^ INF)) return void();
    updata(v << 1, tag[v]), updata(v << 1 | 1, tag[v]), tag[v] = INF;
  }
  void up(int v) {
    ok[v] = ok[v << 1] & ok[v << 1 | 1];
    su[v] = su[v << 1] + su[v << 1 | 1];
    mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
    cx[v] = max(cx[v << 1], cx[v << 1 | 1]);
    if (mx[v << 1] > mx[v << 1 | 1]) cx[v] = max(cx[v], mx[v << 1 | 1]);
    if (mx[v << 1] < mx[v << 1 | 1]) cx[v] = max(cx[v], mx[v << 1]);
    size[v] = size[v << 1] * (mx[v << 1] == mx[v]) +
              size[v << 1 | 1] * (mx[v << 1 | 1] == mx[v]);
  }
  void build(int v, int l, int r) {
    mx[v] = INF, size[v] = r - l + 1, tag[v] = INF, cx[v] = -INF;
    if (l == r) return void();
    int mid = l + r >> 1;
    build(v << 1, l, mid), build(v << 1 | 1, mid + 1, r);
  }
  void change(int v, int l, int r, int ql, int qr, int w) {
    if (ql <= l && r <= qr) {
      if (mx[v] <= w)
        return void();
      else if (w >= cx[v])
        return updata(v, w), void();
    }
    int mid = l + r >> 1;
    down(v);
    if (ql <= mid) change(v << 1, l, mid, ql, qr, w);
    if (qr > mid) change(v << 1 | 1, mid + 1, r, ql, qr, w);
    up(v);
  }
} seg[2];
long long query(int v, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    if (seg[0].ok[v] && seg[1].ok[v])
      return seg[0].su[v] + seg[1].su[v];
    else if (l == r || !seg[0].su[v] || !seg[1].su[v])
      return 0;
  }
  int mid = l + r >> 1;
  seg[0].down(v), seg[1].down(v);
  if (qr <= mid) return query(v << 1, l, mid, ql, qr);
  if (ql > mid) return query(v << 1 | 1, mid + 1, r, ql, qr);
  return query(v << 1, l, mid, ql, qr) + query(v << 1 | 1, mid + 1, r, ql, qr);
}
signed main() {
  int n = 1e5;
  seg[0].build(1, 1, n), seg[1].build(1, 1, n);
  for (int T = read(); T--;) {
    int opt = read(), l = read(), r = read() - 1, x;
    if (opt == 1)
      x = read(), seg[x > 0].change(1, 1, n, l, r, abs(x));
    else
      cout << query(1, 1, n, l, r) << '\n';
  }
  return signed();
}
