Description
In problem 13364, you found that it's not a good idea to challenge your mom on programming.
Thus, you decide to lock your videos using a locker.
The rule of your password is easy while efficient:
First, you'll be given a number n, and you'll use n to get a binary string Sn, following the representation:
S0 = "0"Si = (Si-1) + ("1") + (reverse(invert(Si-1)))fori > 0
Reverse means that after such a function, the order of the binary string will be reversed(e.g., reverse(100) -> 001).
Invert means that after such a function, all the bits will become its inverse(e.g., invert(011)-> 100).
For example, S1 is "011", and S2 is "0111001".
Next, there will be given T indexes k, indicating the position of choosing element in the decoded binary string Sn.
So, your job is to print all the Sn[k], which implies your final password.
I hope there is no "Mom, don't do that 3.0" in the future orz......
Input
The first line is N(1 <= N <= 20) and T(1<= T <= 30), separated by white space.
The next T lines are the index of chosen element, k(1 < k < len(Sn)).
Output
For each test case, print "0" or "1' according to the decoded binary string and the index.
You have to print a '\n' in each line.