<PREV Problem:
NEXT>
Solved by 49 users: defrager, dan, WsemirZ, DAV, JohnJones_001, Fat, topspin, Robert_Gerbicz, avg79, zloy_mipt, UdH-WiNGeR, RAVEman, kornakovBSU, Zhukov_Dmitry, Rizvanov, Darii, orban, daniel.ugra, ilyakor, Kuznetsov_S, zhuojie, Philip_PV, moon5ckq, TTLovePP, Yagi_Arthur, DPR-pavlin, fetetriste, FordPerfect, Dest, EAA2008, ignat, ripatti, abortmozga.ru, s01A15, regmar, mukel, vitar, ethanhunt, Madiyar_Tktl, shvets_175, LiuChenheng, NIGHTFIT, mikelan, bush, Nevermore, demidenko, murphy, Avitella, noh4h_ss.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

brackets 2

Time limit = 3 second(s)

Memory limit = 64 Mb

You are given a string consisting of the brackets "<",">"; "(",")"; "{","}"; "[","]" and a series of N pairs of integers "i j" (1 ≤ ij106)

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*106.

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

Author:

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 23.20.166.68