Cerința

Se dă o stivă inițial vidă. Să se efectueze Q operații de forma:

1 x: Se adaugă x în stivă.
2: Se șterge elementul din vârful stivei.
3 S: Se întreabă dacă se poate scrie valoarea S ca sumă de elemente aflate în stivă. Fiecare element poate fi folosit o singură dată în calcularea sumei. Răspunsul va fi 1 în caz afirmativ și 0 în caz negativ.

Date de intrare

Fișierul de intrare qstiva.in conține pe prima linie numărul Q, iar pe următoarele Q linii se vor afla operațiile descrise mai sus.

Date de ieșire

Fișierul de ieșire qstiva.out va conține răspunsurile operațiilor de tipul 3, câte un răspuns pe linie, în ordinea în care acestea apar în fișierul de intrare.

Restricții și precizări

• 1 ≤ Q ≤ 100000
• pentru o operație de tipul 1, 1 ≤ x ≤ 1000
• pentru o operație de tipul 3, 1 ≤ S ≤ 1000
• nu se vor efectua operații de tipul 2 sau de tipul 3 dacă stiva este goală.

Exemplu:

qstiva.in

8
1 12
2
1 1
3 2
1 2
1 12
3 13
2

qstiva.out

0
1