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;
int const K = 333;
int const N = 100100;
int const INF = 1 << 30;
int type[N], jahdskjhsdj[N], lkjljzxlcjlk[N], blockMax[N], blockMin[N], xs[N],
    mx[N], mn[N], value[N];
int main() {
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d%d%d", type + i, jahdskjhsdj + i, lkjljzxlcjlk + i);
    if (type[i] == 1) {
      scanf("%d", value + i);
    }
  }
  for (int i = 0; i < N; i++) {
    mx[i] = INF;
    mn[i] = -INF;
  }
  for (int from = 0; from < q; from += K) {
    int to = std::min(q, from + K);
    int cn = 0;
    xs[cn++] = N;
    for (int i = 0; i < to; i++) {
      xs[cn++] = jahdskjhsdj[i];
      xs[cn++] = lkjljzxlcjlk[i];
    }
    std::sort(xs, xs + cn);
    cn = (int)(std::unique(xs, xs + cn) - xs);
    std::fill(blockMax, blockMax + cn, INF);
    std::fill(blockMin, blockMin + cn, -INF);
    for (int i = 0, j = 0; i < N; i++) {
      if (xs[j] == i) {
        ++j;
      }
      blockMax[j] = std::min(blockMax[j], mx[i]);
      blockMin[j] = std::max(blockMin[j], mn[i]);
    }
    for (int i = from; i < to; i++) {
      int lb = (int)(std::lower_bound(xs, xs + cn, jahdskjhsdj[i]) - xs) + 1;
      int rb = (int)(std::lower_bound(xs, xs + cn, lkjljzxlcjlk[i]) - xs) + 1;
      if (type[i] == 1) {
        int k = value[i];
        if (k > 0) {
          for (int j = lb; j < rb; j++) {
            blockMax[j] = std::min(blockMax[j], k);
          }
        } else {
          for (int j = lb; j < rb; j++) {
            blockMin[j] = std::max(blockMin[j], k);
          }
        }
      } else {
        long long ans = 0;
        for (int j = lb; j < rb; j++) {
          if (blockMax[j] != INF && blockMin[j] != -INF) {
            ans += (long long)(blockMax[j] - blockMin[j]) * (xs[j] - xs[j - 1]);
          }
        }
        printf("%lld\n", ans);
      }
    }
    for (int i = 0, j = 0; i < N; i++) {
      if (xs[j] == i) ++j;
      mx[i] = std::min(mx[i], blockMax[j]);
      mn[i] = std::max(mn[i], blockMin[j]);
    }
  }
}
