Gary has a special string of booleans A (contains 0 and 1 only), which splits every second into two parts i.e. A and its ones complement A'. Further in this process A and A' gets concatenated and make a new boolean string (i.e. new string is concatenation of A and A').
Initially at 0th second, A contains a single boolean value '0'.
Two integers N and K will be given to us. The above process stops only after Nth second. And till then we must have gotten a large string S consisting of 0s and 1s. Gary is interested to know the Kth boolean value of string S i.e. after process stops.
For eg. if N = 1 and K = 1, you need to tell the 1st boolean value of string that is obtained after 1st process. The string that we'll get after 1st process is "01", so the 1st boolean value is 0.
Note : Counting of N and K starts from 1.
Input contains two space separated integers N and K .
Return the Kth boolean value after Nth second from the string .
Sample Input 1:
Sample Output 1:
Sample Input 2:
Sample Output 2:
Sample Input 3:
Sample Output 3:
Login to submit your solution