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.
import java.util.*;
import java.io.IOException;

public class Test {
    long readLong() {
        long ans = 0;
        boolean neg = false;
        try {
            boolean start = false;
            for (int c = 0; (c = System.in.read()) != -1; ) {
                if (c == '-') {
                    start = true;
                    neg = true;
                    continue;
                } else if (c >= '0' && c <= '9') {
                    start = true;
                    ans = ans * 10 + c - '0';
                } else if (start) break;
            }
        } catch (IOException e) {
        }
        return neg ? -ans : ans;
    }

    final int N = 100_000, B = 316;
    long[][] a = new long[2][N + B], b = new long[2][B + 1];
    long[] sum = new long[B + 1];
    int[][] sz = new int[2][B+1], cur = new int[2][B+1];
    boolean[][] zeros = new boolean[2][B + 1];
    long[][][] c = new long[2][B+1][B];

    void upd(long[] a1, int p, long v) {
        if (a1[p] == 0 || a1[p] > v) a1[p] = v;
    }

    void push(int k) {
        int from = k*B, to = from + B;
        for (int i = 0; i < 2; i++) {
            long v = b[i][k];
            if (v == 0) continue;
            long[] a1 = a[i];
            for (int j = from; j < to; j++) {
                upd(a1, j, v);
            }
            b[i][k] = 0;
        }
    }

    void pull(int k) {
        int from = k*B, to = from + B;
        for (int i = 0; i < 2; i++) {
            long[] a0 = a[i], a1 = a[i ^ 1];
            zeros[i][k] = false;
            for (int j = from; j < to; j++)
                if (a0[j] == 0) {
                    zeros[i][k] = true;
                    break;
                }
            if (zeros[i][k]) continue;
            long[] c1 = c[i][k];
            int top = 0;
            for (int j = from; j < to; j++)
                if (a1[j] != 0) c1[top++] = a0[j];
            Arrays.sort(c1, 0, top);
            sz[i][k] = cur[i][k] = top;
        }
        sum[k] = 0;
        for (int i = from; i < to; i++)
            if (a[0][i] != 0 && a[1][i] != 0)
                sum[k] += a[0][i] + a[1][i];
    }

    void upd_block(int which, int k, long v) {
        long old = b[which][k];
        if (old == 0 || old > v) b[which][k] = v;
        else return;
        if (zeros[which][k]) {
            push(k);
            pull(k);
        } else {
            long[] c1 = c[which][k];
            int n = sz[which][k] - cur[which][k];
            if (n > 0) sum[k] -= (old - v)*n;
            int i = cur[which][k] - 1;
            while (i >= 0)
                if (c1[i] >= v) {
                    sum[k] -= (c1[i] - v);
                    i--;
                } else break;
            cur[which][k] = i + 1;
        }
    }

    long query(int ll, int rr) {
        rr--;
        int from_block = ll / B, to_block = rr / B;
        long ans = 0;
        push(from_block);
        pull(from_block);
        while (ll <= rr && ll / B == from_block) {
            if (a[0][ll] != 0 && a[1][ll] != 0) ans += a[0][ll] + a[1][ll];
            ll++;
        }
        if (ll <= rr) {
            push(to_block);
            pull(to_block);
            while (ll <= rr && rr / B == to_block) {
                if (a[0][rr] != 0 && a[1][rr] != 0) ans += a[0][rr] + a[1][rr];
                rr--;
            }
        }
        for (int i = from_block + 1; i < to_block; i++) ans += sum[i];
        return ans;
    }

    void update(int which, int ll, int rr, long v) {
        rr--;
        int from_block = ll / B, to_block = rr / B;
        long[] a1 = a[which];
        while (ll <= rr && ll / B == from_block) {
            upd(a1, ll, v);
            ll++;
        }
        push(from_block);
        pull(from_block);
        if (ll <= rr) {
            while (ll <= rr && rr / B == to_block) {
                upd(a1, rr, v);
                rr--;
            }
            push(to_block);
            pull(to_block);
        }
        for (int i = from_block + 1; i < to_block; i++) upd_block(which, i, v);
    }

    void start() {
        for (int i = 0; i < 2; i++) Arrays.fill(zeros[i], true);

        long q = readLong();
        while (q > 0) {
            q--;
            int type = (int) readLong(), ll = (int) readLong(), rr = (int) readLong();
            if (type == 1) {
                long v = readLong();
                update(v > 0 ? 0 : 1, ll - 1, rr - 1, Math.abs(v));
            } else {
                System.out.println(query(ll - 1, rr - 1));
            }
        }
    }

    public static void main(String[] args) {
        new Test().start();
    }
}