Požar

문제

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 (X_i, Y_i) raširenosti A_i nalazi se na svim poljima (x, y) za koja vrijedi max(|X_i - x|, |Y_i - y|) < A_i.

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

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 T_i.

입력

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 X_i, Y_i i A_i (1 ≤ X_i ≤ N, 1 ≤ Y_i ≤ M, 1 ≤ A_i ≤ 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 X_i, Y_i i A_i (1 ≤ X_i ≤ N, 1 ≤ Y_i ≤ M, 1 ≤ A_i ≤ 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 T_i (0 ≤ T_i ≤ 2000) koji odgovara i-tom upitu vatrogasaca.

출력

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

힌트

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.

ΔΔΔΔΔΔ....
ΔΔΔΔΔΔ....
ΔΔΔΔΔΔ....
ΔΔΔΔΔΔΔ...
.ΔΔΔΔΔΔΔ..
..ΔΔΔΔΔ...
...ΔΔΔ....
....Δ.....

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

14
29
41

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

11
18
24
25

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

15
25
34