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 ms = 100100;
const int bs = 1000;
const int bu = ms / bs + 2;
const int INF = 0x3f3f3f3f;
bool cmp(std::pair<int, int> a, std::pair<int, int> b) {
  return a.first < b.first;
}
class MinUpdate {
 public:
  void print(int l, int r) {
    for (int i = l; i <= r; i++) {
      propagate(i / bs);
      std::cout << vals[i / bs][i % bs] << ' ';
    }
    std::cout << '\n';
  }
  MinUpdate() {
    for (int i = 0; i < bu; i++) {
      for (int j = 0; j < bs; j++) {
        sum[i][j] = 0;
        vals[i][j] = 0;
        l_vals[i][j] = std::pair<int, int>(0, j);
      }
      sum[i][bs] = 0;
      pt[i] = INF;
      clean[i] = true;
    }
  }
  long long qry(int l, int r) {
    int lb = l / bs;
    int rb = r / bs;
    long long ans = 0;
    if (lb == rb) {
      propagate(lb);
      for (int i = l % bs; i <= r % bs; i++) ans += vals[lb][i];
    } else {
      propagate(lb);
      propagate(rb);
      for (int i = l % bs; i < bs; i++) ans += vals[lb][i];
      for (int i = 0; i <= r % bs; i++) ans += vals[rb][i];
      for (int i = lb + 1; i < rb; i++) {
        int idx = std::lower_bound(l_vals[i], l_vals[i] + bs,
                                   std::pair<int, int>(pt[i], 0), cmp) -
                  l_vals[i];
        ans += sum[i][idx] + (long long)(bs - idx) * pt[i];
      }
    }
    return ans;
  }
  void insert(int pos, int val) {
    int bucket = pos / bs;
    pos = pos % bs;
    propagate(bucket);
    get(bucket, pos, pos);
    assert(temp[0][0].first == 0 && temp[0][0].second == pos);
    temp[0][0].first = val;
    std::merge(temp[0], temp[0] + size[0], temp[1], temp[1] + size[1],
               l_vals[bucket], cmp);
    clean[bucket] = false;
    propagate(bucket);
  }
  void upd(int l, int r, int val) {
    int lb = l / bs;
    int rb = r / bs;
    if (lb == rb) {
      upd(lb, l % bs, r % bs, val);
    } else {
      upd(lb, l % bs, bs - 1, val);
      upd(rb, 0, r % bs, val);
      for (int i = lb + 1; i < rb; i++) {
        clean[i] = false;
        pt[i] = std::min(pt[i], val);
      }
    }
  }

 private:
  void propagate(int bucket) {
    if (clean[bucket]) return;
    for (int i = 0; i < bs; i++) {
      if (l_vals[bucket][i].first > pt[bucket]) {
        l_vals[bucket][i].first = pt[bucket];
      }
      sum[bucket][i + 1] = sum[bucket][i] + l_vals[bucket][i].first;
      vals[bucket][l_vals[bucket][i].second] = l_vals[bucket][i].first;
    }
    pt[bucket] = INF;
    clean[bucket] = true;
  }
  void upd(int bucket, int l, int r, int val) {
    propagate(bucket);
    get(bucket, l, r);
    for (int i = 0; i < size[0]; i++) {
      if (temp[0][i].first > val) {
        temp[0][i].first = val;
        clean[bucket] = false;
      }
    }
    if (!clean[bucket]) {
      std::merge(temp[0], temp[0] + size[0], temp[1], temp[1] + size[1],
                 l_vals[bucket], cmp);
      propagate(bucket);
    }
  }
  void get(int bucket, int l, int r) {
    size[0] = size[1] = 0;
    for (int i = 0; i < bs; i++) {
      int to;
      if (l <= l_vals[bucket][i].second && l_vals[bucket][i].second <= r) {
        to = 0;
      } else
        to = 1;
      temp[to][size[to]++] = l_vals[bucket][i];
    }
  }
  bool clean[bu];
  long long sum[bu][bs + 1];
  int vals[bu][bs];
  std::pair<int, int> l_vals[bu][bs];
  int pt[bu];
  std::pair<int, int> temp[2][bs];
  int size[2];
};
MinUpdate problem[2];
MinUpdate trans[2];
int main() {
  std::set<int> needs[2];
  for (int i = 0; i < ms; i++) needs[0].insert(i);
  needs[1] = needs[0];
  int q;
  std::cin >> q;
  while (q--) {
    int t, l, r;
    scanf("%i %i %i", &t, &l, &r);
    l--;
    r -= 2;
    if (t == 1) {
      int k;
      scanf("%i", &k);
      int on;
      if (k < 0) {
        on = 0;
        k = -k;
      } else {
        on = 1;
      }
      std::set<int>::iterator it1 = needs[on].lower_bound(l);
      std::set<int>::iterator it2 = needs[on].upper_bound(r);
      for (std::set<int>::iterator it = it1; it != it2; it++) {
        if (needs[1 - on].count(*it) == 0) {
          problem[on].insert(*it, k);
          problem[1 - on].insert(*it, trans[1 - on].qry(*it, *it));
        } else {
          trans[on].insert(*it, k);
        }
      }
      needs[on].erase(it1, it2);
      trans[on].upd(l, r, k);
      problem[on].upd(l, r, k);
    } else {
      std::cout << problem[0].qry(l, r) + problem[1].qry(l, r) << '\n';
    }
  }
}
