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.
** 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 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".
* $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
h2. Date de intrare
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ț.
Fișierul de intrare $eso.in$ ...
h2. Date de ieșire
Î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").
În fișierul de ieșire $eso.out$ ...
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 |
| 2
100 100 2
S 50 50
M 50 50
100 100 2
S 50 50
M 50 10
| 1
0
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
