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;
struct ext {
  int mx, sec, cnt, tag, car;
  long long sum;
} tree[2][400050];
void update(int node, int bol) {
  int lft = node << 1, rgt = node << 1 | 1;
  tree[bol][node].sum = tree[bol][node << 1].sum + tree[bol][node << 1 | 1].sum;
  if (tree[bol][lft].mx == tree[bol][rgt].mx) {
    tree[bol][node].mx = tree[bol][lft].mx;
    tree[bol][node].cnt = tree[bol][lft].cnt + tree[bol][rgt].cnt;
    tree[bol][node].sec = max(tree[bol][lft].sec, tree[bol][rgt].sec);
    return;
  }
  if (tree[bol][lft].mx > tree[bol][rgt].mx) {
    tree[bol][node].mx = tree[bol][lft].mx;
    tree[bol][node].cnt = tree[bol][lft].cnt;
    tree[bol][node].sec = max(tree[bol][lft].sec, tree[bol][rgt].mx);
    return;
  }
  swap(lft, rgt);
  tree[bol][node].mx = tree[bol][lft].mx;
  tree[bol][node].cnt = tree[bol][lft].cnt;
  tree[bol][node].sec = max(tree[bol][lft].sec, tree[bol][rgt].mx);
  return;
}
void build(int node, int st, int en, int bol) {
  tree[bol][node].tag = -1;
  tree[bol][node].sum = 0;
  tree[bol][node].car = (1 << 30);
  if (st == en) {
    tree[bol][node].mx = 0;
    tree[bol][node].sec = -1;
    tree[bol][node].cnt = 0;
    tree[bol][node].sum = 0;
    return;
  }
  int mid = (st + en) >> 1;
  build(node << 1, st, mid, bol);
  build(node << 1 | 1, mid + 1, en, bol);
  update(node, bol);
}
void modi(int node, int st, int en, int val, int bol) {
  if (tree[bol][node].mx <= val) return;
  if (val > tree[bol][node].sec) {
    tree[bol][node].tag = val;
    tree[bol][node].sum -=
        1LL * (tree[bol][node].mx - val) * tree[bol][node].cnt;
    tree[bol][node].mx = val;
    return;
  }
  int mid = (st + en) >> 1;
  modi(node << 1, st, mid, val, bol);
  modi(node << 1 | 1, mid + 1, en, val, bol);
  update(node, bol);
}
void down(int node, int st, int en, int bol) {
  if (tree[bol][node].tag == -1) return;
  int mid = (st + en) >> 1;
  modi(node << 1, st, mid, tree[bol][node].tag, bol);
  modi(node << 1 | 1, mid + 1, en, tree[bol][node].tag, bol);
  tree[bol][node].tag = -1;
}
void modify(int node, int st, int en, int l, int r, int val, int bol) {
  if (st >= l and en <= r) {
    tree[bol][node].car = min(tree[bol][node].car, val);
    modi(node, st, en, val, bol);
    return;
  }
  int mid = (st + en) >> 1;
  down(node, st, en, bol);
  int lft = node << 1, rgt = lft | 1;
  if (!(st > r or mid < l)) modify(lft, st, mid, l, r, val, bol);
  if (!(mid + 1 > r or en < l)) modify(rgt, mid + 1, en, l, r, val, bol);
  update(node, bol);
}
void modify2(int node, int st, int en, int l, int v, int carr, int bol) {
  if (st > l or en < l) return;
  carr = min(carr, tree[bol][node].car);
  if (st == en) {
    tree[bol][node].mx = min(v, carr);
    tree[bol][node].cnt = 1;
    tree[bol][node].sec = -1;
    tree[bol][node].sum = tree[bol][node].mx;
    return;
  }
  down(node, st, en, bol);
  int mid = (st + en) >> 1;
  if (l <= mid)
    modify2(node << 1, st, mid, l, v, carr, bol);
  else
    modify2(node << 1 | 1, mid + 1, en, l, v, carr, bol);
  update(node, bol);
}
long long query(int node, int st, int en, int l, int r, int bol) {
  if (st > r or en < l) return 0;
  if (st >= l and en <= r) return tree[bol][node].sum;
  int mid = (st + en) >> 1;
  down(node, st, en, bol);
  long long ret = 0;
  ret += query(node * 2, st, mid, l, r, bol);
  ret += query(node * 2 + 1, mid + 1, en, l, r, bol);
  return ret;
}
set<int> s[2];
set<int>::iterator it;
int lim = 100000;
int dig[2][100005];
void func(int l, int r, int p, int j) {
  while (1) {
    it = s[p].lower_bound(l);
    if (it == s[p].end()) break;
    if (*it > r) break;
    int g = *it;
    s[p].erase(g);
    dig[p][g] = j;
    if (dig[p][g] && dig[p ^ 1][g]) {
      modify2(1, 1, lim, g, j, (1 << 30), p);
      modify2(1, 1, lim, g, dig[p ^ 1][g], (1 << 30), p ^ 1);
    }
  }
}
int main() {
  int i, j, k, l, m, n = lim, ty, p;
  cin >> m;
  build(1, 1, n, 0);
  build(1, 1, n, 1);
  for (int i = 1; i <= n; i++) {
    s[0].insert(i);
    s[1].insert(i);
  }
  while (m--) {
    scanf("%d%d%d", &ty, &l, &k);
    k--;
    if (ty == 2) {
      long long ans = query(1, 1, n, l, k, 0) + query(1, 1, n, l, k, 1);
      printf("%lld\n", ans);
      continue;
    }
    scanf("%d", &j);
    if (j < 0)
      p = 1;
    else
      p = 0;
    func(l, k, p, abs(j));
    modify(1, 1, n, l, k, abs(j), p);
  }
}
