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 ≤ N ≤ 400,000) 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₁, Y₁) and its top-right corner at (X₂, Y₂) (−10⁵ ≤ X₁ < X₂ ≤ 10⁵, −10⁵ ≤ Y₁ < Y₂ ≤ 10⁵). 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_xi, s_yi) (−10⁵ ≤ s_xi, s_yi ≤ 10⁵), and will then fly in a straight line at a constant velocity of d_xi horizontal units and d_yi vertical units per second (−10⁵ ≤ d_xi, d_yi ≤ 10⁵). No ship is stationary – that is, |d_xi| + |d_yi| > 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 ≤ M ≤ 400,000) steps. The i-th step can be of one of two types, given by the value of A_i (1 ≤ A_i ≤ 2):

• A_i = 1: First, wait B_i (0 ≤ B_i ≤ 5000) seconds after the previous step, and then set off a charge to deal C_i (1 ≤ C_i ≤ 10⁵) 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..C_i (1 ≤ B_i ≤ C_i ≤ 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% of the points, N ≤ 500 and M ≤ 2000.

Input Format

The first line of input consists of two space-separated integers N and M.
The second line consists of four space-separated integers X₁, Y₁, X₂, and Y₂
The next N lines each consist of four space-separated integers s_xi, s_yi, d_xi, and d_yi, for i = 1..N.
The next M lines each consist of three space-separated integers A_i, B_i, and C_i, for i = 1..M.

Output Format

For each step in the input where A_i = 2, output a single integer on a separate line – the total amount of damange 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 3rd 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 1st 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.