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 read() {
  int a = 0;
  char c = getchar();
  bool f = 0;
  while (!isdigit(c)) {
    f = c == '-';
    c = getchar();
  }
  while (isdigit(c)) {
    a = a * 10 + c - 48;
    c = getchar();
  }
  return f ? -a : a;
}
const long long _ = 1e5 + 7, INF = 1e18;
struct segTr {
  long long mx[_ << 2], cnt[_ << 2], nxt[_ << 2], sum[_ << 2], mrk[_ << 2];
  bool in[_ << 2];
  void init(long long x, long long l, long long r) {
    mrk[x] = mx[x] = INF;
    cnt[x] = r - l + 1;
    if (l != r) {
      init((x << 1), l, ((l + r) >> 1));
      init((x << 1 | 1), ((l + r) >> 1) + 1, r);
    }
  }
  void mark(long long x, long long val) {
    if (mx[x] <= val) return;
    sum[x] -= in[x] * mx[x] * cnt[x];
    mrk[x] = mx[x] = val;
    in[x] = 1;
    sum[x] += val * cnt[x];
  }
  void down(long long x) {
    mark((x << 1), mrk[x]);
    mark((x << 1 | 1), mrk[x]);
    mrk[x] = INF;
  }
  void up(long long x) {
    mx[x] = max(mx[(x << 1)], mx[(x << 1 | 1)]);
    cnt[x] = (mx[x] == mx[(x << 1)]) * cnt[(x << 1)] +
             (mx[x] == mx[(x << 1 | 1)]) * cnt[(x << 1 | 1)];
    nxt[x] =
        max(mx[x] == mx[(x << 1)] ? nxt[(x << 1)] : mx[(x << 1)],
            mx[x] == mx[(x << 1 | 1)] ? nxt[(x << 1 | 1)] : mx[(x << 1 | 1)]);
    in[x] = in[(x << 1)] & in[(x << 1 | 1)];
    sum[x] = sum[(x << 1)] + sum[(x << 1 | 1)];
  }
  void modify(long long x, long long l, long long r, long long L, long long R,
              long long val) {
    if (mx[x] <= val) return;
    if (l >= L && r <= R)
      if (nxt[x] < val)
        return mark(x, val);
      else {
        down(x);
        modify((x << 1), l, ((l + r) >> 1), L, R, val);
        modify((x << 1 | 1), ((l + r) >> 1) + 1, r, L, R, val);
        return up(x);
      }
    down(x);
    if (((l + r) >> 1) >= L) modify((x << 1), l, ((l + r) >> 1), L, R, val);
    if (((l + r) >> 1) < R)
      modify((x << 1 | 1), ((l + r) >> 1) + 1, r, L, R, val);
    up(x);
  }
} Tr[2];
long long query(long long x, long long l, long long r, long long L,
                long long R) {
  if ((Tr[0].mx[x] == INF && Tr[0].nxt[x] == 0) ||
      (Tr[1].mx[x] == INF && Tr[1].nxt[x] == 0))
    return 0;
  if (l >= L && r <= R)
    if (Tr[0].in[x] && Tr[1].in[x])
      return Tr[0].sum[x] + Tr[1].sum[x];
    else {
      Tr[0].down(x);
      Tr[1].down(x);
      return query((x << 1), l, ((l + r) >> 1), L, R) +
             query((x << 1 | 1), ((l + r) >> 1) + 1, r, L, R);
    }
  Tr[0].down(x);
  Tr[1].down(x);
  long long sum = 0;
  if (((l + r) >> 1) >= L) sum += query((x << 1), l, ((l + r) >> 1), L, R);
  if (((l + r) >> 1) < R)
    sum += query((x << 1 | 1), ((l + r) >> 1) + 1, r, L, R);
  return sum;
}
long long Q;
signed main() {
  Tr[0].init(1, 1, 1e5);
  Tr[1].init(1, 1, 1e5);
  for (Q = read(); Q; --Q)
    if (read() == 1) {
      long long l = read(), r = read() - 1, val = read();
      bool flg = val < 0;
      if (flg) val *= -1;
      Tr[flg].modify(1, 1, 1e5, l, r, val);
    } else {
      long long l = read(), r = read() - 1;
      printf("%lld\n", query(1, 1, 1e5, l, r));
    }
  return 0;
}
