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>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int oo = 0x3f3f3f3f;
const int maxq = 50100;
const int maxn = 100100;
const int block = 230;
int qn;
int up[maxn + 5], down[maxn + 5];
struct data {
  int ty, l, r, K;
  data() {}
  data(int _ty, int _l, int _r, int _K) : ty(_ty), l(_l), r(_r), K(_K) {}
};
struct que {
  int id, p, up, down;
  que() {}
  que(int _id, int _p, int _up, int _down)
      : id(_id), p(_p), up(_up), down(_down) {}
};
inline bool cmp_up(const que &first, const que &second) {
  return first.up < second.up;
}
inline bool cmp_down(const que &first, const que &second) {
  return first.down < second.down;
}
data q[maxq + 5];
long long ans[maxq + 5];
int n = 100010;
int main() {
  memset(up, oo, sizeof up);
  memset(down, oo, sizeof down);
  scanf("%d", &qn);
  for (int i = 0; i < qn; i += block) {
    int to = min(i + block, qn);
    vector<int> all;
    for (int j = (i), j_end_ = (to); j < j_end_; ++j) {
      scanf("%d%d%d", &q[j].ty, &q[j].l, &q[j].r);
      all.push_back(q[j].l);
      all.push_back(q[j].r);
      if (q[j].ty == 1) scanf("%d", &q[j].K);
    }
    sort((all).begin(), (all).end());
    all.resize(unique((all).begin(), (all).end()) - all.begin());
    static int id[maxn + 5];
    memset(id, -1, sizeof id);
    for (int j = (0), j_end_ = ((int((all).size())) - 1); j < j_end_; ++j)
      for (int k = (all[j]), k_end_ = (all[j + 1]); k < k_end_; ++k) id[k] = j;
    static int block_up[(block << 1) + 5], block_down[(block << 1) + 5];
    static int pos_up[maxn + 5], pos_down[maxn + 5];
    for (int j = (0), j_end_ = (n); j < j_end_; ++j)
      pos_up[j] = pos_down[j] = j;
    sort(pos_up, pos_up + n,
         [&](int first, int second) { return up[first] < up[second]; });
    sort(pos_down, pos_down + n,
         [&](int first, int second) { return down[first] < down[second]; });
    memset(block_up, oo, sizeof block_up);
    memset(block_down, oo, sizeof block_down);
    vector<que> ask;
    for (int j = (i), j_end_ = (to); j < j_end_; ++j) {
      q[j].l = lower_bound((all).begin(), (all).end(), q[j].l) - all.begin();
      q[j].r = lower_bound((all).begin(), (all).end(), q[j].r) - all.begin();
      if (q[j].ty == 1) {
        if (q[j].K > 0)
          for (int k = (q[j].l), k_end_ = (q[j].r); k < k_end_; ++k)
            chkmin(block_up[k], q[j].K);
        else
          for (int k = (q[j].l), k_end_ = (q[j].r); k < k_end_; ++k)
            chkmin(block_down[k], -q[j].K);
      } else {
        for (int k = (q[j].l), k_end_ = (q[j].r); k < k_end_; ++k) {
          ask.push_back(que(j, k, block_up[k], block_down[k]));
        }
      }
    }
    sort((ask).begin(), (ask).end(), cmp_up);
    static long long sum[(block << 1) + 5], sum_in[(block << 1) + 5];
    static int cnt[(block << 1) + 5], cnt_in[(block << 1) + 5];
    memset(sum, 0, sizeof sum);
    memset(sum_in, 0, sizeof sum_in);
    memset(cnt, 0, sizeof cnt);
    memset(cnt_in, 0, sizeof cnt_in);
    for (int k = (0), k_end_ = (n); k < k_end_; ++k)
      if (~id[k]) {
        ++cnt[id[k]];
        if (down[k] < oo) ++cnt_in[id[k]];
      }
    int j = 0;
    for (auto u : ask) {
      while (j < n && up[pos_up[j]] < u.up) {
        if (~id[pos_up[j]]) {
          sum[id[pos_up[j]]] += up[pos_up[j]];
          --cnt[id[pos_up[j]]];
          if (down[pos_up[j]] < oo) {
            sum_in[id[pos_up[j]]] += up[pos_up[j]];
            --cnt_in[id[pos_up[j]]];
          }
        }
        ++j;
      }
      if (u.up < oo) {
        if (u.down < oo) {
          ans[u.id] += sum[u.p] + (long long)cnt[u.p] * u.up;
        } else {
          ans[u.id] += sum_in[u.p] + (long long)cnt_in[u.p] * u.up;
        }
      } else {
        if (u.down < oo)
          ans[u.id] += sum[u.p];
        else
          ans[u.id] += sum_in[u.p];
      }
    }
    sort((ask).begin(), (ask).end(), cmp_down);
    memset(sum, 0, sizeof sum);
    memset(sum_in, 0, sizeof sum_in);
    memset(cnt, 0, sizeof cnt);
    memset(cnt_in, 0, sizeof cnt_in);
    for (int k = (0), k_end_ = (n); k < k_end_; ++k)
      if (~id[k]) {
        ++cnt[id[k]];
        if (up[k] < oo) ++cnt_in[id[k]];
      }
    j = 0;
    for (auto u : ask) {
      while (j < n && down[pos_down[j]] < u.down) {
        if (~id[pos_down[j]]) {
          sum[id[pos_down[j]]] += down[pos_down[j]];
          --cnt[id[pos_down[j]]];
          if (up[pos_down[j]] < oo) {
            sum_in[id[pos_down[j]]] += down[pos_down[j]];
            --cnt_in[id[pos_down[j]]];
          }
        }
        ++j;
      }
      if (u.down < oo) {
        if (u.up < oo) {
          ans[u.id] += sum[u.p] + (long long)cnt[u.p] * u.down;
        } else {
          ans[u.id] += sum_in[u.p] + (long long)cnt_in[u.p] * u.down;
        }
      } else {
        if (u.up < oo)
          ans[u.id] += sum[u.p];
        else
          ans[u.id] += sum_in[u.p];
      }
    }
    for (int k = (0), k_end_ = (n); k < k_end_; ++k)
      if (~id[k])
        chkmin(up[k], block_up[id[k]]), chkmin(down[k], block_down[id[k]]);
  }
  for (int i = (0), i_end_ = (qn); i < i_end_; ++i)
    if (q[i].ty == 2)
      printf(
          "%"
          "ll"
          "d\n",
          ans[i]);
  return 0;
}
