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 inf = 0x3f3f3f3f;
const int N = 1e5 + 5;
const int Lim = 1e5;
int read() {
  int s = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    s = s * 10 + c - '0';
    c = getchar();
  }
  return s * f;
}
int n, m;
struct Tree {
  long long sum;
  int tag[2], Min1, Min2, Max1, Max2, NumMin, NumMax;
};
struct Segment_Tree {
  Tree t[N * 4];
  void updateMax(int p, int v) {
    t[p].sum -= 1ll * t[p].NumMin * (v - t[p].Min1);
    t[p].Min1 = v;
  }
  void updateMin(int p, int v) {
    t[p].sum += 1ll * t[p].NumMax * (v - t[p].Max1);
    t[p].Max1 = v;
  }
  void Pushup(int p) {
    int l = p << 1, r = p << 1 | 1;
    t[p].sum = t[l].sum + t[r].sum;
    t[p].tag[0] = t[l].tag[0] & t[r].tag[0];
    t[p].tag[1] = t[l].tag[1] & t[r].tag[1];
    t[p].Min1 = min(t[l].Min1, t[r].Min1);
    t[p].Min2 = min(t[l].Min2, t[r].Min2);
    t[p].NumMax = 0;
    t[p].Max1 = max(t[l].Max1, t[r].Max1);
    t[p].Max2 = max(t[l].Max2, t[r].Max2);
    t[p].NumMin = 0;
    if (t[l].Min1 != t[p].Min1)
      t[p].Min2 = min(t[p].Min2, t[l].Min1);
    else
      t[p].NumMin += t[l].NumMin;
    if (t[r].Min1 != t[p].Min1)
      t[p].Min2 = min(t[p].Min2, t[r].Min1);
    else
      t[p].NumMin += t[r].NumMin;
    if (t[l].Max1 != t[p].Max1)
      t[p].Max2 = max(t[p].Max2, t[l].Max1);
    else
      t[p].NumMax += t[l].NumMax;
    if (t[r].Max1 != t[p].Max1)
      t[p].Max2 = max(t[p].Max2, t[r].Max1);
    else
      t[p].NumMax += t[r].NumMax;
  }
  void Pushdown(int p) {
    int l = p << 1, r = p << 1 | 1;
    if (t[p].Max1 < t[l].Max1) updateMin(l, t[p].Max1);
    if (t[p].Max1 < t[r].Max1) updateMin(r, t[p].Max1);
    if (t[p].Min1 > t[l].Min1) updateMax(l, t[p].Min1);
    if (t[p].Min1 > t[r].Min1) updateMax(r, t[p].Min1);
  }
  void Build(int p, int l, int r) {
    if (l == r) {
      t[p].Min1 = -inf;
      t[p].Max1 = inf;
      return;
    }
    int mid = (l + r) >> 1;
    Build(p << 1, l, mid);
    Build(p << 1 | 1, mid + 1, r);
    Pushup(p);
  }
  void Update(int p) {
    if (t[p].tag[0] && t[p].tag[1]) {
      t[p].NumMax = t[p].NumMin = 1;
      t[p].sum = t[p].Max1 - t[p].Min1;
    }
  }
  void Max(int x, int y, int v, int p, int l, int r) {
    if (y < l || x > r || t[p].Min1 >= v) return;
    if (x <= l && r <= y && t[p].Min2 > v && t[p].tag[0]) {
      updateMax(p, v);
      return;
    }
    if (l == r) {
      t[p].Min1 = v;
      t[p].tag[0] = 1;
      Update(p);
      return;
    }
    int mid = (l + r) >> 1;
    Pushdown(p);
    Max(x, y, v, p << 1, l, mid);
    Max(x, y, v, p << 1 | 1, mid + 1, r);
    Pushup(p);
  }
  void Min(int x, int y, int v, int p, int l, int r) {
    if (y < l || x > r || t[p].Max1 <= v) return;
    if (x <= l && r <= y && t[p].Max2 < v && t[p].tag[1]) {
      updateMin(p, v);
      return;
    }
    if (l == r) {
      t[p].Max1 = v;
      t[p].tag[1] = 1;
      Update(p);
      return;
    }
    int mid = (l + r) >> 1;
    Pushdown(p);
    Min(x, y, v, p << 1, l, mid);
    Min(x, y, v, p << 1 | 1, mid + 1, r);
    Pushup(p);
  }
  long long Query(int x, int y, int p, int l, int r) {
    if (y < l || x > r) return 0;
    if (x <= l && r <= y) return t[p].sum;
    int mid = (l + r) >> 1;
    Pushdown(p);
    return Query(x, y, p << 1, l, mid) + Query(x, y, p << 1 | 1, mid + 1, r);
  }
} tree;
int main() {
  n = read();
  tree.Build(1, 1, Lim);
  for (int i = 1; i <= n; i++) {
    int op = read(), l = read(), r = read() - 1;
    if (op == 1) {
      int x = read();
      if (x < 0) tree.Max(l, r, x, 1, 1, Lim);
      if (x > 0) tree.Min(l, r, x, 1, 1, Lim);
    }
    if (op == 2) printf("%lld\n", tree.Query(l, r, 1, 1, Lim));
  }
  return 0;
}
