Година 2079. Младите се враќаат во Скопје, и има огромна побарувачка за градење на нови куќи во градот. Арно ама, во Скопје тогаш веќе има многу споменици. Притоа, истите може да се дислоцираат, но државата мора да се обесштети за нивната дислокација.

Во оваа задача, ќе претпоставиме дека градот Скопје е претставен како голема правоаголна површина на која, на одредени позиции, во моментов се наоѓаат споменици. Притоа, за секој споменик, позната ни е и цената за негова дислокација.

За службите на градот Скопје да можат ефикасно да ги информираат инвеститорите кои се заинтересирани за градба за можноста тие да откупат одредено земјиште (во форма на правоаголник), потребно е да напишете програма која ефикасно ќе одговара на следното прашање: “За дадена правоаголна површина во градот, колку е вредноста на сите споменици кои се наоѓаат во таа површина?”

Влез

Во првата линија е запишан еден цел број N (1 <= N <= 100 000), кој го означува бројот на споменици во градот. Во секоја од следните N линии се запишани по три броја Xi, Yi (0 <= Xi, Yi <= 10 000 000) и Vi (1 <= Vi <= 10 000), кои ја означуваат позицијата (Xi, Yi) на i-тиот споменик, и неговата цена за дислокација Vi (во евра). Во влезните податоци, можно е да постојат повеќе различни споменици кои се наоѓаат на иста позиција (X, Y) – на пример, воин на коњ и фонтана, итн.

Во следната линија е запишан еден цел број K (1 <= K <= 30 000), кој го означува бројот на прашања (потенцијални површини) за кои е потребно да ја пресметате вредноста на спомениците кои се наоѓаат во секоја од нив. Во следните K линии се запишани по четири цели броеви DXi, DYi, GXi и GYi (0 <= DXi <= GXi <= 10 000 000, 0 <= DYi <= GYi <= 10 000 000), кои ја даваат позицијата и димензиите на правоаголната површина за i-тото барање - притоа, (DXi, DYi) се координатите на темето на правоаголната површина кое се наоѓа долу-лево, додека (GXi, GYi) се координатите на темето на површината кое се наоѓа горе-десно. (Овие две темиња се доволни за да се определи позицијата на површината, бидејќи рабовите на површината се паралелни со рабовите на целата градска површина).

Забелешка: Во тест случаи кои носат најмалку 30% од поените, N и K ќе бидат цели броеви помали или еднакви на 100.

Излез

За секоја од K-те потенцијални површини, отпечатете по еден цел број, кој ја означува вкупната цена за дислокација на спомениците кои се наоѓаат во таа површина (во евра).

Секое од прашањата се одговара независно од сите останатите според погорното објаснување.

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 512 megabytes

Примери

влез
3
1 1 10
3 5 20
1 1 40
2
0 0 2 2
1 1 10 10

излез
50
70

Објаснување за првиот пример: За површината определена со дијагонално спротивните темиња (0, 0) и (2, 2), цената за дислокација на спомениците кои се наоѓаат во неа е 50. Во другата површина се наоѓаат сите три споменици, па вредноста е 10+20+40=70.