Tsubasa-chan adoră dulciurile! De curând a apărut un nou tip de desert. Astfel decide să înfăptuiască o nouă fabrică care să producă acest produs delicios. Fabrica conține un container imens pătratic, plin de aluat, de 106 x 106 unități. Fiecare punct din container are drept coordonate o pereche de numere reale (x, y), unde 0 ≤ x, y ≤ 106, iar fiecare punct are o dulceață. Dulceața unui punct este un număr real, inițial 0. Pentru fabricarea desertului este nevoie de Q operații, care pot fi de următoarele tipuri:

• O îndulcire verticală, determinată de o coordonată xu întreagă și o valoare întreagă v. După această operație, toate punctele din container (x, y) unde xu ≤ x < xu + 1 devin mai dulci cu v.
• O îndulcire orizontală, determinată de o coordonată yu întreagă și o valoare întreagă v. După această operație, toate punctele din container (x, y) unde yu ≤ y < yu + 1 devin mai dulci cu v.
• O degustare, determinată de 4 coordonate întregi xq, yq, xq', yq'. Pentru aceeastă operație, Tsubasa ia o lingură, o pune în aluat la punctul (xq, yq), și apoi o duce in linie dreaptă la punctul (xq', yq'). Mișcarea se efectuează într-o secundă, cu viteză constantă. După aceea, Tsubasa gustă desertul, vrând să afle dulceața totală a aluatului din lingură. Această valoare se calculează în felul următor: dacă lingura trece prin zone de dulceața d1 pentru t1 secunde, de dulceață d2 pentru t2 secunde, …, și de dulceață dk pentru tk secunde, atunci dulceața totală din lingură este t1 • d1 + t2 • d2 + … + tk • dk. Nu se modifică dulceața din container.

Cerința

Dându-se toate operațiile întreprinse în producerea desertului, să se găsească dulcețurile totale ce sunt găsite la toate operațiile de degustare.

Date de intrare

Pe prima linie a fișierului de intrare dulciuri.in se va găsi numărul Q de operații.

Pe următoarele Q linii urmează descrieri a tuturor operațiilor, câte una pe linie, în ordine. O operație este codificată în felul următor:

• O îndulcire verticală este codificată prin 1 xu v.
• O îndulcire orizontală este codificată prin 2 yu v.
• O degustare este codificată prin 3 xq yq xq' yq'.

Date de ieșire

În fișierul de ieșire dulciuri.out, să se afișeze toate rezultatele degustărilor, în ordine, câte una pe linie. Rezultatul unei degustări se consideră a fi corect daca eroarea absolută sau relativă față de soluția comisiei este cel mult 10-7.

Restricții și precizări

• Toate coordonatele din datele de intrare sunt întregi în intervalul [0, 1.000.000].
• 0 ≤ v ≤ 1000.
• v este întreg.
• 1 ≤ Q ≤ 100.000.
• Pentru 20 de puncte nu se fac îndulciri orizontale și Q ≤ 2000.
• Pentru 20 de puncte, la fiecare degustare, fie xq = xq' sau yq = yq', Q ≤ 2000
• Pentru 10 de puncte, se face cel mult o degustare
• Pentru 20 de puncte, toate degustările se fac după toate îndulcirile
• Pentru 10 de puncte, Q ≤ 2000
• Pentru 20 de puncte, fără restricții suplimentare

Exemplul 1:

dulciuri.in

3
1 2 60
2 3 60
3 0 0 3 4

dulciuri.out

35

Explicație

Situația pentru degustarea din primul exemplu este explicată în diagrama de mai jos.

Zonele roz sunt zonele în care s-a aplicat o îndulcire, și numerele reprezintă cu cât s-a îndulcit. Zona din intersecția îndulcirilor are dulceața 120. Linia diagonală punctată reprezintă traseul.

Traseul are lungimea \( \sqrt{3^2 + 4^2} = 5 \), și este completat într-o secundă – astfel are viteza de 5 unități pe secundă. Segmentul de la (2, 2.(6)) la (2.25, 3) are lungimea \( \sqrt{(2.25 – 2)^2 + (2.(6) – 3)^2} = \sqrt{¼^2 + (1/3)^2} = 5/12 \), și are dulceața 60 – astfel el este traversat în (5/12) x (1/5) = 1/12 secunde, și contribuie cu (1/12) x 60 = 5 la dulceața totală. Segmentul de la (2.25, 3) la (3, 4) are lungimea \( \sqrt{(3 – 2.25)^2 + (4 – 3)^2} = 5/4 \), și are dulceața 120 – astfel el este traversat în (5/4) x (1/5) = 1/4 secunde, și contribuie cu (1/4) x 120 = 30 la dulceața totală. Astfel, cum segmentul de la (0, 0) la (2, 2.(6)) contribuie cu 0, dulceața totală este 35.

Exemplul 2:

dulciuri.in

4
1 2 10
3 2 0 2 1
3 3 0 3 1
3 2 0 2 0

dulciuri.out

10
0
10

Explicație

Situația pentru degustările din al doilea exemplu este explicată în diagrama de mai jos.

În primul traseu (cel din stânga) trecem mereu printr-o zonă cu dulceața 10, deci rezultatul degustării este 10. În al doilea traseu (cel din dreapta) trecem mereu printr-o zonă cu dulceața 0, deci rezultatul degustării este 0. În al treilea traseu, stăm pe loc pentru o secundă într-o zona de dulceață 10, deci răspunsul este 10.

Exemplul 3:

dulciuri.in

6
1 4 413
1 3 234
2 5 244
2 3 777
3 1 2 14 15
3 31 4 2 40

dulciuri.out

128.3076923077
29.0881226054