Problem description

Master Ramzel wygrał kolejny kontest. Tym razem jego główny przeciwnik bart320 był niebezpiecznie blisko w rankingu. Aby w przyszłości zminimalizować ryzyko porażki, Ramzel postanowił wybudować na swojej kwadratowej działce ośrodek treningowy. W ramach przygotowań zakupił maszynę, która umie przygotować kwadratową powierzchnię o boku długości 1 metra pod budowę ośrodka. Dla wygody planowania podzielił swoją działkę na kwadraty o boku długości 1 metra i dla każdego z nich oszacował czas, jaki maszyna będzie potrzebować do przygotowania tego terenu.

Master Ramzel, jak to ma w zwyczaju, nie lubi geometrii, dlatego piękno geometryczne bryły ośrodka zostanie drastycznie ograniczone. Postanowił, że ośrodek treningowy będzie miał kształt równoramiennego trójkąta prostokątnego o przyprostokątnych równoległych do boków działki. Może się więc okazać, że nie każdy kwadrat, który należy przygotować pod budowę, będzie w całości zajęty przez ośrodek, ale Ramzel się tym nie przejmuje. Chciałby też, żeby odległość przyprostokątnych podstawy ośrodka od równoległych boków działki wyrażona w metrach była liczbą całkowitą. W najdłuższej ścianie planuje zamontować ogromne okno, przez które będzie podziwiał jezioro znajdujące się za północno-wschodnim rogiem działki. Ośrodek będzie więc tak ustawiony, żeby róg przy przyprostokątnych był w południowo-zachodniej części budynku.

Master Ramzel nie jest pewny, gdzie wybuduje ośrodek. Przygotował wiele planów budowy. Każdy plan to współrzędne południowo-zachodniego rogu ośrodka i długość krótszych boków. Chciałby poznać dla każdego planu ilość czasu, jaką potrzebuje maszyna, żeby przygotować teren pod budowę. Master Ramzel ma tylko jedną maszynę, więc czas potrzebny do przygotownania terenu pod budowę ośrodka to suma czasów przygotowań kwadratowych terenów, na których będzie wybudowany ośrodek.

Napisz program, który: wczyta opis działki i planów, dla każdego z planów obliczy czas potrzebny do przygotowania terenu i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się dodatnia liczba całkowita N określająca długość boku działki. W kolejnych N wierszach znajduje się opis działki. i-ty wiersz zawiera N dodatnich liczb całkowitych c_i, 1, c_i, 2, …, c_i, n poddzielanych pojedynczymi odstępami, oznaczających czas potrzebny maszynie na przygotowanie danego pola.

W kolejnym wierszu znajduje się dodatnia liczba całkowita Q oznaczająca liczbę planów. W kolejnych Q wierszach znajduje się opis planów, po jednym w wierszu. Opis każdego planu składa się z trzech dodatnich liczb całkowitych x_i, y_i, d_i pooddzielanych pojedynczymi odstępami. x_i oraz y_i oznaczają współrzędne rogu ośrodka, a d_i długość przyprostokątnych ośrodka.

Zagwarantowane jest, że każdy planowany ośrodek mieści się w granicach działki.

Wyjście

Należy wypisać Q wierszy. W i-tym wierszu powinna się znaleźć jedna liczba – czas potrzebny maszynie w i-tym planie.

Ograniczenia

1 ≤ N ≤ 1 000, 1 ≤ Q ≤ 1 000 000, 1 ≤ c_i, j ≤ 1 000.

Podzadania

W testach wartych łącznie 10% punktów dodatkowo zachodzą warunki N ≤ 100, Q ≤ 1 000.

W innych testach wartych łącznie 40% punktów d_i jest stałe i niezależne od i.

Przykład

4
1 3 4 1 
2 3 2 6 
9 5 3 4
7 2 3 8
3
1 4 2
3 2 2
3 3 1

18
12
3