simulare

Cerință

Se dă o matrice $m$ cu $N$ linii și $M$ coloane care conține valori. Se dă și un șir de $Q$ direcții (nord, vest, sud, est). Plecând de la un punct $(x_0, y_0)$ și urmând toate direcțille date, pe rând, se va forma un drum $(x_1, y_1), (x_2, y_2), \dots, (x_Q, y_Q)$. Pentru fiecare $i$ ($1 \leq i \leq Q$) să se afișeze $m_{x_1, y_1} + m_{x_2, y_2} + \dots + m_{x_i, y_i}$.

Date de intrare

Pe prima linie se găsesc cinci numere întregi, $N$, $M$, $Q$, $x_0$ și $y_0$. Pe următoarele $N$ linii, se găsesc câte $M$ numere întregi, reprezentând valorile din matrice. Pe următoarea linie, se găsesc $Q$ carcatere, care pot fi N, E, S sau V, reprezentând direcțiile pe baza cărora se construiește drumul.

Din cauza mărimii datelor de intrare, vă recomandăm să adăugați aceste linii la începutul funcției main():

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

Date de ieșire

Pe prima linie se vor găsi $Q$ numere, reprezentând sumele cerute.

Restricții și precizări

• $1 \leq N, M \leq 1 \ 000$
• $1 \leq Q \leq 100 \ 000$
• $1 \leq m_{i, j} \leq 1 \ 000 \ 000 \ 000$, unde $1 \leq i \leq N$ și $1 \leq j \leq M$
• Se garantează că $1 \leq x_i \leq N$ și $1 \leq y_i \leq M$, unde $0 \leq i \leq Q$.

Exemplu

stdin

3 4 8 2 3
1 2 3 4
5 6 7 8
9 10 11 12
SENVVNES

stdout

11 23 31 38 44 46 49 56

Explicație

$m_{3, 3} = 11$
$11 + m_{3, 4} = 23$
$23 + m_{2, 4} = 31$
$31 + m_{2, 3} = 38$
$38 + m_{2, 2} = 44$
$44 + m_{1, 2} = 46$
$46 + m_{1, 3} = 49$
$49 + m_{2, 3} = 56$