Manthan, Codefest 17 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

*3100

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Nagini

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputNagini, 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 10^{5}. 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*, *y*_{1}) and point (*i*, *y*_{2}), such that *y*_{1} > 0 and *y*_{2} < 0. Then, if for any point (*i*, *y*_{3}) containing a snake such that *y*_{3} > 0, *y*_{1} ≤ *y*_{3} holds and for any point (*i*, *y*_{4}) containing a snake such that *y*_{4} < 0, |*y*_{2}| ≤ |*y*_{4}| holds, then the danger value at coordinate *x* = *i* is *y*_{1} + |*y*_{2}|. If no such *y*_{1} and *y*_{2} 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·10^{4}) denoting the number of queries.

Next *q* lines each describe a query. Each query description first contains the query type *type*_{i} (1 ≤ *type*_{i} ≤ 2). This is followed by further description of the query. In case of the type being 1, it is followed by integers *l*_{i}, *r*_{i} and *k*_{i} (, - 10^{9} ≤ *k*_{i} ≤ 10^{9}, *k* ≠ 0). Otherwise, it just contains two integers, *l*_{i} and *r*_{i} (1 ≤ *l*_{i} < *r*_{i} ≤ 10^{5}).

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 *y*_{2} 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 *y*_{2} satisfying the above condition for these coordinates.

Thus, total danger value is 17 + 17 = 34.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/03/2023 01:23:05 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|