Farmer John vuole aiuto dalle mucche per un lago. Mappa pascolo $R$ righe ($3\le R\le100$), $C$ colonne ($3\le C\le100$), quadrati sei per sei piedi, quota media in pollici ($10\le elev_{rc}\le5000$).

Allena «scavare pestando». Mandria robusta copre esattamente $3\times3$, va all’angolo alto sinistro $R_s,C_s$ ($1\le R_s\le R-2;1\le C_s\le C-2$), abbassa $D_s$ pollici ($1\le D_s\le40$). Mucche basse attendono altre al loro livello, quindi non tutte celle pestate o alcune meno.

Quote iniziali, $N$ istruzioni ordinate ($1\le N\le20000$), livello finale $E$ ($0\le E\le5000$): volume in pollici cubi, massimo $2,000,000,000$. Barriere ai bordi impediscono fuoriuscita.

Pascolo $4\times6$, quote con righe/colonne:

Collina alto destra $36$, piccola alto sinistra $28$, lieve depressione mezzo riga $4$. Dopo "$1\;4\;4$":

Solo tre celle scendono, sei altri gruppi aspettavano livello mai raggiunto. Dopo "$1\;1\;10$" alto sinistra:

Livello $22$ pollici dà profondità:

Somma $66$ per area sei per sei piedi: $66\times72\times72=342,144$ pollici cubi, lato $72$ pollici.

Scrivi programma automatico.

Input

• Riga $1$: $R,C,E,N$ separati da spazi.

• Righe $2,\ldots,R+1$: riga $i+1$, fila $i$ con $C$ interi separati da spazi.

• Righe $R+2,\ldots,R+N+1$: riga $i+R+1$, istruzione $i$ con $R_s,C_s,D_s$.

Output

• Riga 1: intero, volume del nuovo lago in pollici cubi.

Esempi

Input 1

4 6 22 2
28 25 20 32 34 36
27 25 20 20 30 34
24 20 20 20 20 30
20 20 14 14 20 20
1 4 4
1 1 10

Output 1

342144

Spiegazione

Come esempio del testo.

Autore: Rob Kolstad, 2008