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 T>
inline bool chkmin(T &x, T y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
inline bool chkmax(T &x, T y) {
  return x < y ? x = y, 1 : 0;
}
template <typename T>
inline void read(T &x) {
  char ch = getchar();
  int f = 1;
  x = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}
int q;
struct SGT {
  long long sum[100050 << 2];
  int all[100050 << 2], lzy[100050 << 2], cnt[100050 << 2],
      maxx[100050 << 2][2];
  void put_min(int u, int w) {
    sum[u] -= 1ll * cnt[u] * maxx[u][0] * all[u];
    chkmin(maxx[u][0], w), chkmin(lzy[u], w);
    sum[u] += 1ll * cnt[u] * maxx[u][0] * (all[u] = 1);
  }
  void push(int u) {
    if (lzy[u] != (1 << 30))
      put_min(u << 1, lzy[u]), put_min(u << 1 | 1, lzy[u]), lzy[u] = (1 << 30);
  }
  void upd(int u, int w) {
    if (w > maxx[u][0])
      swap(maxx[u][0], maxx[u][1]), maxx[u][0] = w;
    else if (w < maxx[u][0] && w > maxx[u][1])
      maxx[u][1] = w;
  }
  void update(int u) {
    all[u] = all[u << 1] & all[u << 1 | 1],
    sum[u] = sum[u << 1] + sum[u << 1 | 1], cnt[u] = 0;
    for (register int i = 0; i <= 1; ++i) maxx[u][i] = -(1 << 30);
    for (register int i = 0; i <= 1; ++i)
      for (register int j = 0; j <= 1; ++j) upd(u, maxx[u << 1 | i][j]);
    for (register int i = 0; i <= 1; ++i)
      cnt[u] += cnt[u << 1 | i] * (maxx[u << 1 | i][0] == maxx[u][0]);
  }
  void build(int u, int l, int r) {
    sum[u] = all[u] = 0, lzy[u] = maxx[u][0] = (1 << 30),
    maxx[u][1] = -(1 << 30), cnt[u] = r - l + 1;
    if (l == r) return;
    build(u << 1, l, ((l + r) >> 1)), build(u << 1 | 1, ((l + r) >> 1) + 1, r);
    update(u);
  }
  void modify(int u, int l, int r, int tl, int tr, int w) {
    if (maxx[u][0] <= w) return;
    if (tl <= l && r <= tr && maxx[u][1] <= w) return put_min(u, w);
    push(u);
    if (tl <= ((l + r) >> 1)) modify(u << 1, l, ((l + r) >> 1), tl, tr, w);
    if (((l + r) >> 1) < tr)
      modify(u << 1 | 1, ((l + r) >> 1) + 1, r, tl, tr, w);
    update(u);
  }
} T[2];
long long query(int u, int l, int r, int tl, int tr) {
  if (!T[0].sum[u] || !T[1].sum[u]) return 0;
  if (tl <= l && r <= tr && T[0].all[u] && T[1].all[u])
    return T[0].sum[u] + T[1].sum[u];
  long long ret = 0;
  for (register int i = 0; i <= 1; ++i) T[i].push(u);
  if (tl <= ((l + r) >> 1)) ret += query(u << 1, l, ((l + r) >> 1), tl, tr);
  if (((l + r) >> 1) < tr)
    ret += query(u << 1 | 1, ((l + r) >> 1) + 1, r, tl, tr);
  return ret;
}
int main() {
  int op, l, r;
  read(q);
  for (register int i = 0; i <= 1; ++i) T[i].build(1, 1, 100050);
  while (q--) {
    read(op), read(l), read(r), --r;
    if (op == 1)
      read(op), op > 0 ? T[0].modify(1, 1, 100050, l, r, op)
                       : T[1].modify(1, 1, 100050, l, r, -op);
    else
      printf("%lld\n", query(1, 1, 100050, l, r));
  }
  return 0;
}
