With the Death Star reduced to stardust, the evil Galactic Empire has been forced to pull out all stops in their fight against the rebels. $N$ $(1\le N\le 400000)$ heavily-armed Imperial starships have been deployed to fly across the galaxy, destroying all rebel resistance in their paths. All hope would seem lost, but the rebels have a powerful new Jedi ally on their side… and his name is John Cena.

John Cena has devised a plan to deal massive amounts of damage to the Imperial squadron. Upon studying stolen flight plans, he's realized that all of the enemy ships will always stay within a single plane of space. Then, treating it as a 2D Cartesian plane, he's set up a "blast zone" – a rectangle with its bottom-left corner at coordinates $(X_1,Y_1)$ and its top-right corner at $(X_2,Y_2)$ $(-{10}^5\le X_1<X_2\le {10}^5,-{10}^5\le Y_1<Y_2\le {10}^5)$. He has access to a device which can set off a powerful electrical charge throughout the blast zone, damaging ships within it (including ones right on its border)!

As mentioned, John Cena has access to the Imperial flight plans, which happen to be quite simple. The $i$-th ship will initially be located at coordinates $(s_{x_i},s_{y_i})$ $(-{10}^5\le s_{x_i},s_{y_i}\le {10}^5)$, and will then fly in a straight line at a constant velocity of $d_{x_i}$ horizontal units and $d_{y_i}$ vertical units per second $(-{10}^5\le d_{x_i},d_{y_i}\le {10}^5)$. No ship is stationary – that is, $|d_{x_i}|+|d_{y_i}|>0$. Additionally, multiple ships may occupy the same location at any point in time.

Now, John Cena's battle plan will consist of $M$ $(1\le M\le 400000)$ steps. The $i$-th step can be of one of two types, given by the value of $A_i$ $(1\le A_i\le 2)$:

• $A_i=1$: First, wait $B_i$ $(0\le B_i\le 5000)$ seconds after the previous step, and then set off a charge to deal $C_i$ $(1\le C_i\le {10}^5)$ damage to each ship which is currently within the blast zone (inclusively)
• $A_i=2$: To assess success, determine the total amount of damage dealt so far to ships $B_i\dots C_i$ $(1\le B_i\le C_i\le N)$

John Cena's time is now, but can you help him determine the results of each of his steps of type $2$?

Note: In cases worth $20\mathrm{\%}$ of the points, $N\le 500$ and $M\le 2000$.

Input Specification

The first line of input consists of two space-separated integers $N$ and $M$.
The second line consists of four space-separated integers $X_1$, $Y_1$, $X_2$, and $Y_2$.
The next $N$ lines each consist of four space-separated integers $s_{x_i}$, $s_{y_i}$, $d_{x_i}$, and $d_{y_i}$, for $i=1\dots N$.
The next $M$ lines each consist of three space-separated integers $A_i$, $B_i$, and $C_i$, for $i=1\dots M$.

Output Specification

For each step in the input where $A_i=2$, output a single integer on a separate line – the total amount of damage dealt so far to ships in the range specified by $B_i$ and $C_i$. Note that each result may not fit within a 32-bit signed integer.

Sample Input

3 14
-2 -1 3 3
7 2 -2 0
-1 -6 1 2
-1 0 0 3
1 0 5
1 1 7
2 1 2
2 1 3
1 1 1
1 0 1
2 1 3
1 1 30
1 2 6
1 1 1000
2 1 1
2 2 2
2 3 3
2 2 3

Sample Output

0
12
14
32
30
12
42

Explanation

The first charge is set off immediately, and the second occurs $1$ second later - during both of these, only the $3$rd ship is within the blast zone, so it takes $12$ damage. The next $2$ charges both occur $1$ second after that, at which point the $3$ ships are at coordinates $(3,2)$, $(1,-2)$ and $(-1,6)$, respectively – as such, only the $1$st ship is hit, sustaining $2$ damage. The following charge deals $30$ damage to both ships $1$ and $2$, while neither of the last $2$ charges hit any ships.