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[4][N + B], b = new long[4][B + 1], sum = new long[4][B + 1];
    int[][] cur = new int[4][B+1];
    long[][][] c = new long[4][B+1][B];

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

    void push(int p, int k) {
        if (b[p][k] != -1) {
            int from = k*B, to = from + B;
            long v = b[p][k];
            long[] a1 = a[p];
            for (int j = from; j < to; j++) {
                upd(a1, j, v);
            }
            b[p][k] = -1;
        }
    }

    void pull(int p, int k) {
        int from = k*B, to = from + B;
        long[] a1 = a[p], c1 = c[p][k];
        int top = 0;
        long s1 = 0;
        for (int j = from; j < to; j++)
            if (a1[j] != -1) {
                c1[top++] = a1[j];
                s1 += a1[j];
            }
        Arrays.sort(c1, 0, top);
        cur[p][k] = top;
        sum[p][k] = s1;
    }

    void upd_block(int p, int k, long v) {
        long old = b[p][k];
        if (old == -1 || old > v) b[p][k] = v;
        else return;
        long[] c1 = c[p][k];
        int n = B - cur[p][k];
        if (old == -1) old = 0;
        long s1 = sum[p][k];
        if (n > 0) s1 -= (old - v)*n;
        int top = cur[p][k] - 1;
        while (top >= 0)
            if (c1[top] >= v) s1 -= (c1[top--] - v);
            else break;
        cur[p][k] = top + 1;
        sum[p][k] = s1;
    }

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

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

    void start() {
        for (int p = 0; p < 4; p++) {
            Arrays.fill(a[p], -1);
            Arrays.fill(b[p], -1);
        }

        long q = readLong();
        while (q > 0) {
            q--;
            int type = (int) readLong(), ll = (int) readLong(), rr = (int) readLong();
            if (type == 1) {
                long v = readLong();
                if (v > 0) {
                    update(0, ll, rr, v);
                    update(1, ll, rr, v);
                    update(3, ll, rr, 0);
                } else {
                    update(2, ll, rr, -v);
                    update(3, ll, rr, -v);
                    update(1, ll, rr, 0);
                }

            } else {
                long ans = 0;
                for (int p = 0; p < 4; p++) {
                    long v = query(p, ll, rr);
                    if (p % 2 == 0) ans += v;
                    else ans -= v;
                }
                System.out.println(ans);
            }
        }
    }

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