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>
const int MAXN = 400010;
const int INF = 0x3f3f3f3f;
struct info {
  int fir, sec, cnt;
  info() { fir = sec = INF; }
} pos[MAXN], neg[MAXN];
info operator+(info a, info b) {
  info res;
  res.fir = std::max(a.fir, b.fir);
  res.cnt = (-(a.fir == res.fir) & a.cnt) + (-(b.fir == res.fir) & b.cnt);
  res.sec = std::max(a.sec, b.sec);
  if (a.fir < res.fir) res.sec = std::max(res.sec, a.fir);
  if (b.fir < res.fir) res.sec = std::max(res.sec, b.fir);
  return res;
}
long long sum[MAXN];
void mkadd(int u, info* tr, int v) {
  if (v < tr[u].fir) {
    sum[u] -= (long long)tr[u].cnt * (tr[u].fir - v);
    tr[u].fir = v;
  }
}
void mkpush(int u, info* tr) {
  mkadd(u << 1, tr, tr[u].fir);
  mkadd(u << 1 | 1, tr, tr[u].fir);
}
void pushdown(int u) { mkpush(u, pos), mkpush(u, neg); }
void update(int u) {
  sum[u] = sum[u << 1] + sum[u << 1 | 1];
  pos[u] = pos[u << 1] + pos[u << 1 | 1];
  neg[u] = neg[u << 1] + neg[u << 1 | 1];
}
void _mdf(int u, int l, int r, int v) {
  if (l == r) {
    if (v > 0)
      pos[u].fir = std::min(pos[u].fir, v), pos[u].sec = 0;
    else
      neg[u].fir = std::min(neg[u].fir, -v), neg[u].sec = 0;
    if (pos[u].fir != INF && neg[u].fir != INF) {
      sum[u] = pos[u].fir + neg[u].fir;
      pos[u].cnt = neg[u].cnt = 1;
    } else
      sum[u] = pos[u].cnt = neg[u].cnt = 0;
    return;
  }
  if (v > 0 && v > pos[u].sec) return mkadd(u, pos, v);
  if (v < 0 && -v > neg[u].sec) return mkadd(u, neg, -v);
  int mid = l + r >> 1;
  pushdown(u);
  _mdf(u << 1, l, mid, v);
  _mdf(u << 1 | 1, mid + 1, r, v);
  update(u);
}
void mdf(int u, int l, int r, int L, int R, int v) {
  if (L <= l && r <= R) return _mdf(u, l, r, v);
  int mid = l + r >> 1;
  pushdown(u);
  if (L <= mid) mdf(u << 1, l, mid, L, R, v);
  if (mid < R) mdf(u << 1 | 1, mid + 1, r, L, R, v);
  update(u);
}
long long qry(int u, int l, int r, int L, int R) {
  if (L <= l && r <= R) return sum[u];
  int mid = l + r >> 1;
  long long res = 0;
  pushdown(u);
  if (L <= mid) res += qry(u << 1, l, mid, L, R);
  if (mid < R) res += qry(u << 1 | 1, mid + 1, r, L, R);
  return res;
}
const int RAN = 100000;
int main() {
  std::ios_base::sync_with_stdio(false), std::cin.tie(0);
  int Q;
  std::cin >> Q;
  while (Q-- > 0) {
    int opt, l, r, K;
    std::cin >> opt >> l >> r;
    if (opt == 1)
      std::cin >> K, mdf(1, 1, RAN, l, r - 1, K);
    else
      std::cout << qry(1, 1, RAN, l, r - 1) << '\n';
  }
  return 0;
}
