Mc-A-Mc Mc

Când toate bunoacele care mă văd vor să fie împreuna cu mine așa că îmi introduc prietenul scund într-un mod nonchalant având în căști PetrecereUșaUrmătoare (le-a speriat)

Cerință

Vi se dau numerele naturale $N$, $M$ și o matrice de $N \times M$ formată din numere naturale mai mici sau egale cu $100$. Definim o mișcare cu sensul $ch$ astfel:

Dacă $ch$=>, ne vom muta la dreapta cu o casuță
Dacă $ch$=<, ne vom muta in jos cu o casuță

Vi se dau $Q$ întrebări de forma:

$K, s, S$ unde acestea reprezintă lungimea șirului $s$, un șir de mișcări, respectiv un număr întreg.

Pentru toate cele $Q$ întrebări, să se afișeze DA dacă exista o permutare a șirului de mișcări, începand din căsuța $(1, 1)$, astfel încât suma elementelor prin care am trecut să fie egală cu $S$, altfel să se afișeze NU.

Date de intrare

Pe prima linie se vor găsi trei numere naturale $N$, $M$ și $Q$. Pe următoarele $N$ linii se vor afla câte $M$ valori, care reprezintă matricea. Pe următoarele $Q$ linii se va afla $K$, un șir de mutări $s$ și $S$, care reprezintă cele $Q$ întrebări.

Dacă folosiți citire cu std::cin, vă recomandăm să adăugați aceste linii la începutul programului:

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

Date de ieșire

Pe urmatoarele $Q$ linii se vor afla raspunsurile la întrebări.

Restricții și precizări

• $2 \leq N, M \leq 500$;
• $1 \leq mat_{i, j} \leq 100, 1 \leq i \leq N, 1 \leq j \leq M$;
• $1 \leq Q \leq 10 \ 000$;
• $1 \leq K \leq N+M-2$;
• $1 \leq S \leq (N+M-1) \cdot 100$;
• Se garanteaza ca în șirurile $s$, $<$ va apărea de maxim $N-1$ ori și $>$ va apărea de maxim $M-1$ ori;

Exemplul 1

stdin

3 4 6
7 8 9 1
1 15 3 4
5 4 3 6
2 >> 24
2 >> 23
2 <> 30
5 ><>>< 37
3 ><> 26
3 ><> 500

stdout

DA
NU
DA
DA
DA
NU

Explicație

Pentru primele două întrebări, oricum am permuta șirul de mutări, mereu vom parcurge matricea astfel: $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3)$, iar suma va fi $7+8+9=24$.
Pentru a treia întrebare, dacă permutăm șirul de mutări ca fiind ><, vom trece prin căsuțele matricei în ordinea aceasta: $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2)$, iar suma va fi $7+8+15=30$.