Hard Data Structures > Segment Tree/Interval Tree

Alice and Bob always loves to play different games.One day, they were not finding any game to play and so they were feeling disappointed. Suddenly, they found a book in their room with a binary number written onto it, the length of which was not longer than 100000. Then, They formulate the game rule, say "**Big Binary Game**". In this game, they challenges each others with different binary string modification tasks and operations. So, you can find unlimited fun in their game. There are basically four different types of operations they are going to perform with the binary string, which are: 1 x y z - Replace the digits from x to y to z. here z is either 0 or 1. 2 x - Toggle the character at position x. 3 x - Tell the character at position x. 4 x y z - Determine whether substring of length z starting from x and y are equal. Today, Alice and Bob are playing the Big Binary Game in their room. At first Alice gives any one type of instruction to Bob. Bob performs the instruction do some operation in binary string and then Bob gives next instruction to Alice and so on. Suddenly, you enter into their room. You are a very big fan of Alice and Bob as well as their different games.So,you take so much interest in their Big Binary Game. Now, its your task to simulate the entire game process assuming Alice starts the game first. For every operation of type 3 and 4, firstly print the name of the player ( "**Alice** " or "**Bob** " ) who gives the instruction at that step of the game and then for operation of type 3 print the **xth** character of binary string at that step and for the operation of type 4 print the word "**wins**" if resultant substrings are equal otherwise print "**loses**". **if any one of the substring does not exist then it is considered as "loses" situation**. See the sample I/O for more clarity. Input: ------ Input starts with an integer **T (1<=T<=10)**, denoting the number of test cases. Each case contains a binary string probably with leading zeros, which is a binary integer in the range of **100000 bit biginteger number**. Then next line contain an integer **Q(1<=Q<=100000)** denoting total steps of game they will play. Then for every steps of the game there will be a line of input denoting the any of the above mentioned four type of operation. All the indexing of the operations are 1 based. Output: ------- For each case of input for every operation of type 3 and 4 print the output as described in the problem statement. Sample Input ------------ 1 1110001110001 6 4 1 4 3 1 4 5 1 3 5 4 1 4 3 2 6 4 1 4 3 Sample Output ------------- Alice loses Alice 1 Bob loses Bob wins

Bishal Gautam