nandu-and-monsters-3

Nandu is stuck in a maze consisting of N rooms. Each room with room number x has a door leading into room number 2x (if 2x ≤ N) and another door leading into room number 2x+1 (if 2x+1 ≤ N). All these doors are 2-way doors ie. they can be opened from both the sides.

Some of these N rooms have monsters living in them. 

Nandu is currently in room number i . Nandu's only escape from this maze is to somehow reach room number j which contains the magical Wish-Granting Well. The Well will only grant a wish to Nandu if he offers it a single golden coin. Nandu presently has only a single golden coin in his possession. However, if while going from room number i to j he meets a monster, the monster will take away the only golden coin Nandu has and Nandu will never be able to escape from the maze. 

You will be given information about every room telling you whether a monster resides in it or not. You will then be given Q scenarios, each scenario describing the locations i (the room currently Nandu is present in)  and j (the room where the wishing well is present), i and j will vary over different scenarios but the locations of the monsters will remain fixed for all these scenarios. For each of these scenarios, you have to find out whether Nandu can escape from the maze or not.

Input :

The first line consists on N and Q denoting the number of rooms in the maze and the number of different scenarios that will be given to you. The next line consists of N non-space separated integers such that if the kth integer is '0' , there is no monster present in room number k and if the kth integer is '1' , there is a monster present in room number k. The next Q lines are such that each line consists of two space separated integers i and j denoting Nandu's current location and the location of the Wishing Well for  this particular scenario respectively.

Output :

For every scenario print on a new line 'Yes' if Nandu can escape from the maze and 'No' if he cannot escape from the maze. (Quotes for clarity).

Constraints :

1 ≤ N ≤ 100000

1 ≤ Q ≤ 100000

1 ≤ i,j ≤ N

Author : Shreyans

Tester : Sayan

(By IIT Kgp HackerEarth Programming Club)

SAMPLE INPUT
3 9
001
1 2
1 3
3 2
2 1
2 3
3 1
1 1
2 2
3 3

SAMPLE OUTPUT
Yes
No
No
Yes
No
No
Yes
Yes
No

Explanation

A monster is present only in room number 3. 

Scenario 1 : Nandu is initially present in room number 1 and the Wish-Granting Well is present in room number 2 . Since there is no monster in either of the rooms Nandu goes from 1 -> 2 without losing his golden coin. Hence Nandu can escape the maze by making a wish to the Wish-Granting Well

Scenario 2 : Nandu goes from 1 -> 3. However, there is a monster present in room number 3, which takes away his only golden coin before he can make a wish to the Wish-Granting Well. Hence Nandu cannot escape the maze.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
'''f=open('input.txt')
g=open('output.txt', 'w')
nooftest=int(f.readline().strip())'''
#import cmath
import math
#import time
n,test=list(map(int,input().split()))
monster=input()
array=[]
for j in range(n):
	i=j+1
	if i==1:
		array.append(-1)
	elif i%2==0:
		array.append(i/2)
	else:
		array.append((i-1)/2)
for i in range(test):
	start,final=list(map(int,input().split()))
	levelstart=int(math.log(start,2))+1
	levelfinal=int(math.log(final,2))+1
	done=0
	if levelfinal<levelstart:
		while levelstart!=levelfinal:
			if monster[start-1]=='1':
				print("No")
				done=1
				break
			else:
				start=array[start-1]
				levelstart-=1
	elif levelfinal>levelstart:
		while levelstart!=levelfinal:
			if monster[final-1]=='1':
				print("No")
				done=1
				break
			else:
				final=array[final-1]
				levelfinal-=1
	if done==0:
		while final!=start:
			if monster[final-1]=='1' or monster[start-1]=='1':
				print("No")
				done=1
				break
			else:
				final=array[final-1]
				start=array[start-1]
		if done==0 and monster[start-1]=='1':
			print("No")
		elif done==0:
			print("Yes")


N, Q = [int(_) for _ in input().split()]
maze = input()
for i in range(Q):
	s, e = [int(_) for _ in input().split()]
	s, e = max(s, e), min(s, e)
	if maze[s-1] == '1' or maze[e-1] == '1':
		print('No')
	else:
		ans = True
		while s != e:
			if s < e:
				s, e = e, s
			else:
				s /= 2
				if maze[s-1] == '1':
					ans = False
					break
		print('Yes' if ans else 'No')
	


N,Q=list(map(int,input().split()))
Monsters=input()
def escape(P,M):
	if Monsters[M-1]=="1" or Monsters[P-1]=="1":
		print("No")
	elif P==M:
		print("Yes")
	else:
		if P>M:
			P=int(P/2)
		else:
			M=int(M/2)
		escape(P,M)
		
for i in range(Q):
	P,M=list(map(int,input().split()))
	escape(P,M)
	
		


def LCA(arr,i,j):
	path1=[i]
	path2=[j]
	while(i/2>0):
		path1.append(int(i/2))
		i/=2
	while(j/2>0):
		path2.append(int(j/2))
		j/=2
	lca=1
	for i in range(0,max(len(path1),len(path2))+1):
		if path1[len(path1)-i-1]!=path2[len(path2)-i-1]:
			return [path1[0:len(path1)-i+1],path2[0:len(path2)-i+1]]
	
#~ print LCA([1,2,3,4,5,6,7,8,9,10,11],1,1)

def check(n,q,monsters,rooms):
	for i in range(len(rooms)):
		a = rooms[i][0]
		b = rooms[i][1]
		if(a!=b):
			path1,path2 = LCA(n,a,b)
			flag = 0
			for node in path1:
				if monsters[node-1]==1:
					flag+=1
					break
			for node in path2:
				if monsters[node-1]==1:
					flag+=1
					break
			if flag>0:
				print("No")
			else:
				print("Yes")
		else:
			if monsters[a-1]==1:
				print("No")
			else:
				print("Yes")

n,q = input().split();
n = int(n)
q = int(q)

monsters = input()
monsters = [int(x) for x in monsters]
nodes = []
for i in range(q):
	a,b = input().split();
	a = int(a)
	b = int(b)
	nodes.append((a,b))
check(n,q,monsters,nodes)
	


from math import log
l, t = list(map(int, input().split(" ")))
s = input()
for x in range(t):
	start, end = list(map(int, input().split(" ")))
	if(start<=end):
		big = end
		small = start
	else:
		big = start
		small = end
	counter = 0
	
	while (True):
		if(s[big-1] == '1' or s[small-1]=='1'):
			break
		if(big==small):
			counter = 1
			break
		if(int(log(big, 2)) == int(log(small, 2))):
			small /= 2
		big /= 2
	
	if(counter==1):
		print("Yes")
	else:
		print("No")


lst = list(map(int,input().split()))
n = lst[0]
q = lst[1]

monster = input()

for t in range(q):
	inp = list(map(int,input().split()))
	if inp[0] >= inp[1]:
		i = inp[0]
		j = inp[1]
	else:
		i = inp[1]
		j = inp[0]
	
	temp = i
	root = 1
	path = []
	while (temp >= root and monster[temp-1] != '1'):
		path.append(temp)
		temp = temp/2
	
	temp = j
	while(temp >= root and monster[temp-1] != '1'):
		if temp in path:
			print('Yes')
			break
		temp = temp/2
	
	else:
		print('No')