Un interval de numere naturale poate fi unul dintre intervalele matematice binecunoscute:
(a, b) = {x natural; a < x < b}
(a, b] = {x natural; a < x <= b}
[a, b) = {x natural; a <= x < b}
[a, b] = {x natural; a <= x <= b}
O mulţime de numere naturale poate fi descrisă ca o expresie formată din unul sau mai multe intervale, între oricare două intervale situate pe poziţii consecutive existând o operaţie permisă. Operaţiile permise sunt:
• Intersecţie – desemnată prin litera n
• Reuniune – desemnată prin litera u
• Diferenţă – desemnată prin caracterul – (minus).
Intersecţia are prioritate maximă. Reuniunea şi diferenţa au aceeaşi prioritate, mai mică decât prioritatea intersecţiei. Pentru evaluarea unei expresii se efectuează operaţiile în ordinea descrescătoare a priorităţii; operaţiile cu aceeaşi prioritate se evaluează în ordine de la stânga la dreapta.
De exemplu, expresia
[7,10)u(1,4)n[2,6)-(3,8) = [7,10)u[2,3]-(3,8)
are ca valoare o mulţime de numere întregi, astfel
{x întreg; 2 <= x <= 3 sau 8 <= x <= 9} = {2,3,8,9}
Cerinţă
Dată fiind o succesiune de interogări, fiecare interogare conţinând un număr şi o expresie, să se determine răspunsul pentru fiecare interogare (DA dacă numărul dat aparţine mulţimii rezultate în urma evaluării expresiei, respectiv NU în caz contrar).
Date de intrare
Fişierul de intrare opmult.in conţine pe prima linie numărul natural T care reprezintă numărul de interogări. Fiecare dintre următoarele T linii conţine un număr natural y, urmat de un spaţiu, apoi de o expresie sub forma descrisă în enunţ, reprezentând o interogare.
Date de ieşire
Fişierul de ieşire opmult.out conţine T linii, câte o linie pentru fiecare dintre cele T interogări. Pe linia i va fi scris cuvântul DA dacă pentru a i-a interogare din fişierul de intrare numărul y aparţine mulţimii rezultate în urma evaluării expresiei din interogare, respectiv cuvântul NU în caz contrar.
Restricţii
• 1 ≤ T ≤ 10
• Capetele intervalelor, precum şi numerele din interogări sunt numere naturale din intervalul [1,255].
• Lungimea unei expresii din fişierul de intrare este de maxim 2000 caractere.
• Expresiile nu conţin spaţii.
Exemple
opmult.in
opmult.out
Explicaţii
2
6 [2,6]n[6,20]
4 (1,4)n[2,6)u[7,10)-(3,8)
DA
NU
Există T=2 interogări. [2,6]n[6,20] = [6,6] = {6}, deci răspunsul este DA (1,4)n[2,6)u[7,10)-(3,8) = [2,3]u[7,10)-(3,8) =
={2,3,7,8,9}-{4,5,6,7} = {2,3,8,9}, deci răspunsul este NU