11 kwietnia 4097 roku. Stacje informacyjne podały, że badania zaciemnionej części planety XoX zostały oficjalnie zakończone. Większość lądowników powróciła z próbkami nieznanych substancji.

Po wstępnej analizie laboratoryjnej okazało się, że wśród próbek znajduje się półprzewodnik o wyjątkowych właściwościach fizycznych. O opinię zapytano Eksperta Supermocarstwa Ziemskiego ds. Elektroniki, Alberta Diodę: „Jest to niesamowite odkrycie na skalę międzyplanetarną. Mamy nadzieję, iż nowo poznany pierwiastek znajdzie zastosowanie w konstrukcji komputerów i pozwoli na uzyskanie jeszcze wyższych prędkości procesorów i pamięci. Xiem, bo tak nazwaliśmy tę substancję, może w przyszłości wyprzeć krzem z przemysłu elektronicznego. Pokładamy wysokie nadzieje we współpracy z firmami uczestniczącymi w ekspedycji.”

Niestety, kilka miesięcy później doszło do zatargów pomiędzy korporacjami o prawa do terenów na planecie XoX, a w związku z tym i do zysków ze złóż Xiemu na nich zgromadzonych. Firma „Mech Inc.” uważa, że jej wkład finansowy w badania był najwyższy, dlatego też nie chce się zgodzić na podział działek zaproponowany przez Supermocarstwo Ziemskie. Niestety, nie jest ona odosobniona w swoich osądach, ponieważ każda z pozostałych korporacji również chciałaby uzyskać jak największy zysk z odkrycia. Eksperci każdej z firm mają własną koncepcję podziału terenów, lecz nie sposób jest określić, który z nich jest tym właściwym.

Twoim zadaniem jest pomoc w rozwiązaniu konfliktu poprzez obiektywną ocenę wartości działek zaproponowanych przez wszystkich ekspertów.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1 ≤ N ≤ 20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zawiera liczbę całkowitą n (1 ≤ n ≤ 10⁶) oznaczającą liczbę pomiarów złóż na planecie.

W kolejnych n wierszach podane są ich opisy, składające się z 3 liczb całkowitych rozdzielonych spacją: x, y i w, gdzie wartości x i y (-10⁶ ≤ x, y ≤ 10⁶) odpowiadają położeniu pomiaru na mapie, a w (0 ≤ w ≤ 100) oznacza wartość złóż w danym punkcie pomiarowym.

Następnie podana jest liczba całkowita m (1 ≤ m ≤ 10³), oznaczająca liczbę zapytań znajdujących się w kolejnych m wierszach. Pojedyncze zapytanie składa się z 4 liczb całkowitych: x1, y1, x2 i y2 (-10⁶ ≤ x1, y1, x2, y2 ≤ 10⁶) rozdzielonych spacją, wyznaczających lewy, górny (x1; y1) i prawy, dolny (x2; y2) róg działki.

W przypadku chciwych ekspertów — działka może zostać zdegradowana do wielkości punktu.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu danych są obliczone wartości działek, dla każdego zapytania w oddzielnym wierszu.

Cena terenu liczona jest jako zaokrąglona w dół średnia pomiarów wartości złóż Xiemu na nim zgromadzonych. Pomiary leżące na krawędziach zaliczane są do wnętrza działek.

Przykład
Dane wejściowe

1
5
-2 -2 1
-2 2 4
0 0 3
2 -2 4
2 2 4
3
-3 -3 -1 -1
-3 -3 1 1
-3 -3 3 3

Wynik

1
2
3