Zbog globalnog zatopljenja sve češće ljeti viđamo velike požare. Zaštićena šuma „Matričin lug” smatra se osobito rizičnom pa vatrogasci mole da napišeš program koji će predvidjeti širenje nekoliko požara u toj šumi.

Matričin lug poznat je po tome što se može vizualizirati kao tablica s N redaka i M stupaca. Ono što je manje poznato je da požari u toj šumi uvijek počinju u obliku kvadrata ili romba. Označimo polje u x-tom retku i y-tom stupcu Matričinog luga oznakom (x, y).

Požar koji počinje u obliku kvadrata sa središtem u (Xi, Yi) raširenosti Ai nalazi se na svim poljima (x, y) za koja vrijedi max(|Xi - x|, |Yi - y|) < Ai.

Požar koji počinje u obliku romba sa središtem u (Xi, Yi) raširenosti Ai obuhvaća sva polja (x, y) za koja vrijedi |Xi - x| + |Yi - y| < Ai.

Bez obzira na oblik, obje vrste požara šire se na isti način. Ako u jednoj minuti šuma na nekom polju gori, onda će u sljedećoj minuti goriti i šuma na svim poljima direktno susjednima tom polju. Moguće je da će se početni požari preklapati u nekim poljima šume.

U nultoj minuti gorit će samo područja u kojima počinju požari. Šuma gori jako sporo pa se niti jedno opožareno polje nikada neće ugasiti. Vatrogasce za Q trenutaka zanima koliko će polja šume goriti u minuti Ti.

Ulazni podaci

U prvom su retku dva prirodna broja N i M (1 ≤ N, M ≤ 2000), brojevi iz teksta zadatka.

U sljedećem retku su tri cijela broja: K, R i Q (0 ≤ K, R ≤ 2000, 1 ≤ Q ≤ 2000), redom broj kvadratastih požara, broj rombastih požara i broj upita iz teksta zadatka.

U sljedećih K redaka su po tri prirodna broja Xi, Yi i Ai (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M, 1 ≤ Ai ≤ 2000), redak i stupac središta te raširenost i-tog požara koji započinje u obliku kvadrata.

U sljedećih R redaka su po tri prirodna broja Xi, Yi i Ai (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M, 1 ≤ Ai ≤ 2000), redak i stupac središta te raširenost i-tog požara koji započinje u obliku romba.

U sljedećih Q redaka je po jedan cijeli broj Ti (0 ≤ Ti ≤ 2000) koji odgovara i-tom upitu vatrogasaca.

Izlazni podaci

Potrebno je ispisati Q redaka. U i-tom retku treba ispisati koliko polja šume će gorjeti u minuti Ti.

Probni primjeri

Ulaz

8 10
1 1 3
2 3 2
5 5 2
0
1
2

Izlaz

14
29
41

Opis prvog probnog primjera:

U nultoj minuti požar će se nalaziti samo na crvenim poljima, kojih je 9+5=14. U sljedećoj minuti gorjet će i narančasta polja pa će ukupno gorjeti 14+15=29 polja, a u minuti nakon i žuta polja će gorjeti što je ukupno 29+12=41 polje.

Ulaz

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

Izlaz

11
18
24
25

Ulaz

6 6
1 1 3
1 1 3
6 6 3
0
1
2

Izlaz

15
25
34