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;
template <typename T1, typename T2>
inline T1 max(T1 a, T2 b) {
  return a < b ? b : a;
}
template <typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
  return a < b ? a : b;
}
const char lf = '\n';
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
  if (s == t) {
    t = (s = buf) + fread(buf, 1, bufl, stdin);
    if (s == t) return EOF;
  }
  return *s++;
}
inline int ty() {
  int a = 0;
  int b = 1, c = fetch();
  while (!isdigit(c)) b ^= c == '-', c = fetch();
  while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
  return b ? a : -a;
}
}  // namespace ae86
using ae86::ty;
const int _ = 100007, inf = 0x3f3f3f3f;
struct j2t {
  static const int _t = _ << 2;
  long long sum[_t];
  int t[_t], st[_t], ct[_t], tchan[_t], got[_t];
  void up(int x) {
    got[x] = got[(x << 1)] & got[(x << 1 | 1)],
    sum[x] = sum[(x << 1)] + sum[(x << 1 | 1)];
    t[x] = max(t[(x << 1)], t[(x << 1 | 1)]),
    st[x] = max(t[x] == t[(x << 1)] ? st[(x << 1)] : t[(x << 1)],
                t[x] == t[(x << 1 | 1)] ? st[(x << 1 | 1)] : t[(x << 1 | 1)]);
    ct[x] = ct[(x << 1)] * (t[x] == t[(x << 1)]) +
            ct[(x << 1 | 1)] * (t[x] == t[(x << 1 | 1)]);
  }
  void putchan(int x, int d) {
    if (t[x] <= d) return;
    sum[x] -= 1ll * got[x] * t[x] * ct[x];
    tchan[x] = t[x] = d;
    sum[x] += 1ll * t[x] * ct[x], got[x] = 1;
  }
  void dwn(int x) {
    if (tchan[x] < inf)
      putchan((x << 1), tchan[x]), putchan((x << 1 | 1), tchan[x]),
          tchan[x] = inf;
  }
  void plant(int x, int l, int r) {
    t[x] = tchan[x] = inf, st[x] = -inf, ct[x] = r - l + 1, got[x] = 0,
    sum[x] = 0;
    if (l == r) return;
    plant((x << 1), l, ((l + r) >> 1)),
        plant((x << 1 | 1), ((l + r) >> 1) + 1, r);
  }
  void change(int x, int l, int r, int tl, int tr, int d) {
    if (tr < l || tl > r || t[x] <= d) return;
    if (tl <= l && r <= tr && st[x] <= d) {
      putchan(x, d);
      return;
    }
    dwn(x);
    if (tl <= ((l + r) >> 1)) change((x << 1), l, ((l + r) >> 1), tl, tr, d);
    if (tr > ((l + r) >> 1))
      change((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr, d);
    up(x);
  }
} t[2];
long long finder(int x, int l, int r, int tl, int tr) {
  if (r < tl || l > tr || !t[0].sum[x] || !t[1].sum[x]) return 0;
  if (tl <= l && r <= tr && t[0].got[x] && t[1].got[x])
    return t[0].sum[x] + t[1].sum[x];
  t[0].dwn(x), t[1].dwn(x);
  return finder((x << 1), l, ((l + r) >> 1), tl, tr) +
         finder((x << 1 | 1), ((l + r) >> 1) + 1, r, tl, tr);
}
int n;
int main() {
  ios::sync_with_stdio(0), cout.tie(nullptr);
  n = 100000;
  t[0].plant(1, 1, n), t[1].plant(1, 1, n);
  int qn = ty();
  for (int qq = 1; qq <= qn; qq++) {
    int op = ty(), l = ty(), r = ty() - 1;
    if (op == 1) {
      int a = ty();
      t[a > 0].change(1, 1, n, l, r, max(a, -a));
    } else
      cout << finder(1, 1, n, l, r) << lf;
  }
  return 0;
}
