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, typename U>
inline void chkmax(T& x, U y) {
  if (x < y) x = y;
}
template <typename T, typename U>
inline void chkmin(T& x, U y) {
  if (y < x) x = y;
}
const int N = 100000;
const int M = 320;
const int INF = 1e9 + 7;
vector<pair<int, long long> > V[2][M];
long long d[2][M], dp[2][N], sum[M];
int A[N], B[N], L[N], R[N];
long long get_sum(int l, int r) {
  int s = l / M;
  long long ret = 0;
  for (int i = l; i < r; i++) {
    long long p = min(d[0][s], dp[0][i]);
    long long q = min(d[1][s], dp[1][i]);
    if (p == INF || q == INF) continue;
    ret += p + q;
  }
  return ret;
}
long long calc(int l, int r) {
  int s = l / M, e = (r - 1) / M;
  if (s == e) return get_sum(l, r);
  long long ret = get_sum(l, (s + 1) * M) + get_sum(e * M, r);
  for (int i = s + 1; i < e; i++) ret += sum[i];
  return ret;
}
void renew(int s) {
  int p0 = 0, q0 = 0;
  sum[s] = 0;
  V[0][s].clear(), V[1][s].clear();
  for (int i = s * M; i < N && i < (s + 1) * M; i++) {
    int p = min(d[0][s], dp[0][i]);
    int q = min(d[1][s], dp[1][i]);
    chkmax(p0, p), chkmax(q0, q);
    if (p == INF || q == INF) continue;
    V[0][s].push_back(pair<int, long long>(p, p)),
        V[1][s].push_back(pair<int, long long>(q, q));
    sum[s] += p + q;
  }
  sort((V[0][s]).begin(), (V[0][s]).end()),
      sort((V[1][s]).begin(), (V[1][s]).end());
  for (int i = 1; i < ((int)(V[0][s].size())); i++) {
    V[0][s][i].second += V[0][s][i - 1].second;
    V[1][s][i].second += V[1][s][i - 1].second;
  }
  d[0][s] = p0, d[1][s] = q0;
}
void process(int l, int r, long long k) {
  int flg = (k < 0);
  k = abs(k);
  int s = l / M, e = (r - 1) / M;
  if (s == e) {
    for (int i = l; i < r; i++) chkmin(dp[flg][i], k);
    renew(s);
    return;
  }
  for (int i = l; i < (s + 1) * M; i++) chkmin(dp[flg][i], k);
  renew(s);
  for (int i = e * M; i < r; i++) chkmin(dp[flg][i], k);
  renew(e);
  for (int i = s + 1; i < e; i++) {
    if (d[flg][i] <= k) continue;
    if (d[flg][i] == INF) {
      d[flg][i] = k;
      renew(i);
    } else {
      d[flg][i] = k;
      int j0 = lower_bound(V[0][i].begin(), V[0][i].end(),
                           pair<int, long long>(d[0][i], 0)) -
               V[0][i].begin() - 1;
      int j1 = lower_bound(V[1][i].begin(), V[1][i].end(),
                           pair<int, long long>(d[1][i], 0)) -
               V[1][i].begin() - 1;
      sum[i] = (j0 == -1 ? 0 : V[0][i][j0].second) +
               (((int)(V[0][i].size())) - 1 - j0) * d[0][i] +
               (j1 == -1 ? 0 : V[1][i][j1].second) +
               (((int)(V[1][i].size())) - 1 - j1) * d[1][i];
    }
  }
}
int main() {
  int Q;
  scanf("%d", &Q);
  for (int i = 0; i < N; i++) dp[0][i] = dp[1][i] = INF;
  for (int i = 0; i < (N - 1) / M + 1; i++) d[0][i] = d[1][i] = INF;
  for (int i = 0; i < Q; i++) {
    scanf("%d%d%d", &A[i], &L[i], &R[i]), L[i]--, R[i]--;
    if (A[i] == 1) scanf("%d", &B[i]);
  }
  for (int i = 0; i < Q; i++) {
    if (A[i] == 1)
      process(L[i], R[i], B[i]);
    else
      printf("%lld\n", calc(L[i], R[i]));
  }
  return 0;
}
