Avem un erou care are două resurse principale pe care le poate folosi: Stamina și Mana. La începutul jocului, acesta are $A$ puncte de Stamina și $B$ puncte de Mana. Eroul are la dispoziția sa $N$ abilități, de două tipuri:
* $S X Y$: abilitate care consumă $X$ puncte de Stamina și întoarce $Y$ puncte de Mana. După folosirea abilității, eroul va avea $A - X$ puncte de Stamina și $B + Y$ puncte de Mana
* $M X Y$: abilitate care consumă $X$ puncte de Mana și întoarce $Y$ puncte de Stamina. După folosirea abilității, eroul va avea $B - X$ puncte de Mana și $A + Y$ puncte de Stamina
* $S X Y$: abilitate care consumă $X$ puncte de Stamina și întoarce $Y$ puncte de Mana.
** Poate fi folosită doar dacă $A ≥ X$
** După folosire, eroul va avea $A - X$ puncte de Stamina și $B + Y$ puncte de Mana
* $M X Y$: abilitate care consumă $X$ puncte de Mana și întoarce $Y$ puncte de Stamina
** Poate fi folosită doar dacă $B ≥ X$
** După folosire, eroul va avea $B - X$ puncte de Mana și $A + Y$ puncte de Stamina
Eroul poate folosi o abilitate doar dacă are suficiente puncte din resursa pe care o consumă abilitatea. O abilitate de tip $S$ poate fi folosită doar dacă $A ≥ X$, iar o abilitate de tip $M$ poate fi folosită doar dacă $B ≤ >= X$.
Eroul nu poate ajunge niciodată cu numărul de puncte de Mana sau de Stamina mai mare decât cele inițiale. De exemplu, dacă inițial avem $B$ puncte de Stamina, la momentul actual avem $B1$ puncte de Stamina, și folosim o abilitate care ne întoarce $X$ puncte de Stamina, după folosirea ei vom avea $min(B, B1 + X)$ puncte de Stamina.
h2. Cerință
Să se spună dacă există o combinație de abilități care poate fi folosită astfel încât eroul să nu rămână niciodată fără resurse. Altfel spus, să se spună dacă eroul poate folosi abilități "la infinit".
h2. Date de intrare
Fișierul de intrare $eso.in$ ...
Fișierul de intrare $eso.in$ conține pe prima linie numărul natural [$T$], reprezentând numărul de teste. Pentru fiecare test, se vor găsi pe prima linie trei numere naturale [$A$], $B$ și [$N$], iar pe următoarele $N$ linii se vor găsi abilitățile eroului, sub forma prezentată în enunț.
h2. Date de ieșire
În fișierul de ieșire $eso.out$ ...
În fișierul de ieșire $eso.out$ se vor găsi $T$ linii, pe fiecare linie $i$ fiind răspunsul la cel de-al [$i$]-lea test: $1$ sau $0$ (dacă se poate sau nu ca eroul să folosească abilități "la infinit").
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 10$
* $1 ≤ A, B ≤ 5.000$
* $1 ≤ N ≤ 1.000$
* $1 ≤ X[i], Y[i] ≤ 5.000$
h2. Exemplu
table(example).
|_. eso.in |_. eso.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
100 100 2
S 50 50
M 50 50
100 100 2
S 50 50
M 50 10
| 1
0
|
h3. Explicație
...
Pentru primul test, eroul poate folosi o secvență infinită de abilități: $1, 2, 1, 2, 1, 2, ...$ sau chiar: $1, 1, 2, 2, 1, 1, 2, 2, ...$
Pentru cel de-al doilea test, eroul nu poate folosi abilități la infinit pentru că cea de-a doua abilitate nu întoarce suficiente puncte de Stamina înapoi.
== include(page="template/taskfooter" task_id="eso") ==
