Trip

Eroul nostru, Axiom Postulates, vrea să traverseze un oras, mai periculos. Orașul poate fi reprezentat ca o înșiruire continuă de cartiere, care începe în cartierul $1$ și se termină în cartierul $n$. Din cartierul $k$ poți ajunge doar în cartierul $k + 1$ pentru orice $1 \leq k < n$.

Fiecare cartier poate avea unul dintre următoarele $3$ tipuri:

• Tipul $1$: Cartier Bun, notat prin caracterul o. Când eroul se află în acest cartier, primește un leu de la localnici.
• Tipul $2$: Cartier Normal, notat prin caracterul −. Când eroul se află în acest cartier, nu primește nimic.
• Tipul $3$: Cartier Dubios, notat prin caracterul x. Când eroul se află în acest cartier este jefuit, dar doar de un leu, din mila hoților. Dacă eroul nu are nici măcar un leu, este însărcinat cu datorii. (numărul de lei pe care îl are poate fi și negativ)

Există, de asemenea, și $q$ operații care pot fi de $2$ tipuri:

• Tipul $1$: $1 \ i \ c$ - cartierul $i$ devine un cartier de tip $c$
• Tipul $2$: $2 \ l_1 \ r_1 \ l_2 \ r_2 \ k$ - eroul vrea să își înceapă călătoria într-un cartier din intervalul $[l_1, r_1]$ și să își finalizeze călătoria într-un cartier din intervalul $[l_2, r_2]$. Pentru fiecare astfel de operație, trebuie să aflăm dacă este posibilă o astfel de călătorie, astfel încât la finalul acesteia să aibă exact $k$ lei. La începutul fiecărei călătorii, Axiom are $0$ lei.

Date de intrare

Prima linie conține numărul $n$, reprezentând numărul de caractere respectiv numărul de operații. Pe cea de a doua linie se află $n$ caractere ce reprezintă descierea celor $n$ cartiere, în ordine. Următoarea linie conține numărul $q$ reprezentând numărul de întrebări, iar ultimele $q$ linii cont,in operațiile de tipul $1$ sau $2$.

Date de ieșire

Să se afișeze, pe câte o linie, răspunsul la toate operațiile de tipul $2$. Pentru o operație de tipul $2$ se va afișa $1$ dacă o astfel de călătorie este posibilă și $0$ altfel.

Restricții și precizări

• $1 \leq l_1 \leq r_1 < l_2 \leq r_2 \leq n$
• $|k| \leq 200 \ 000$
• $4 \leq n \leq 200 \ 000$

Exemplu

trip.in

9
x - o x - x o o x
3
2 1 1 6 8 3
1 6 o
2 2 3 5 9 1

trip.out

0
1

Explicații

Pentru prima întrebare, dacă Axiom pornes,te din cartierul $1$, acesta ajunge în cartierul $6$ cu $-2$ lei, cartierul $7$ cu $-1$ leu și în cartierul $8$ cu $0$ lei, deci răspunsul este $0$.

Pentru cea de a doua întrebare, Axiom poate să pornească din cartierul $3$ și ajunge în cartierul $6$ cu $1$ leu, deci răspunsul este $1$.