You are given a string consisting of the brackets "<",">"; "(",")"; "{","}"; "[","]" and a series of N pairs of integers "i j" (1 ≤ i ≤ j ≤ 10^6)
The problem is to determine if a subsequence is a right bracket sequence (RBS)

Here is a definition of RBS: RBS + RBS = RBS; <RBS> = RBS, (RBS) = RBS, [RBS] = RBS, {RBS} = RBS.

The following sequences are RBS: (), ([]), <>()[](<>){{}}, <{{{}}()}>.

Input Sequence of brackets. The length of the sequence does not exceed 106.

N — the number of requests, N ≤ 2*10^6.

N lines with pairs of i and j.

Output N lines with answers: "Y" when subsequence is a RBS, "N" otherwise

Input#1
}<>(){)(<})[]
3
2 3
2 5
8 11
Output#1
Y
Y
N

Input#2
((><))>{<>}[[])
5
2 5
8 11
12 13
12 14
13 14
Output#2
N
Y
N
N
Y

Limita de timp : 3 secunde
Limita de memorie : 64 Mb

sper ca nu are nimic faptul ca am lasat problema in engleza ... nu cred ca vor fi probleme vand in vedere ca suntem .. programatori

edit : unde se mai vede 106 in cod ii 10 la puterea a 6-a
& cred ca 2 saptamani e bin ... cred ca acelas termen lar da si tw8

vad ca nu o poate rezolva nimeni su nu ii acroda nimeni atentie
sa va dau un ajutor (dupa cum vad ca a dat si emi in concursul cu sahul) uitati ce mi-a zis DranaXum intr-un pm
... have fun

Nu am inteles problema:|
...Ce am inteles e ca i e prima paranteza si j ultima, si parantezele dintre ele sa faca parte din :  (), ([]), <>()[](<>){{}}, <{{{}}()}>. 
adica din sirul <>()[](){{}}[[> , daca i=1,j=6 atunci Y (dar la i=9 j=12 tot Y nu? )

pai ideea e ca paranteza de la 6 tre sa o inchida pe cea de la 1 in cazul de mai sus la 1 ai < si la 6 ai ] deci nu e un RBS. un alt exemplu ar fi "()[]()" (tot din secventa ta 3 - 8) se poate vedea ca desi 3 este inchis de 4 5 de 6 si 7 e 8 deci este un RBS

   Pe ABCDomenii: 250MB spatiu + 20GB trafic + 5 subdomenii = 0.95 €