Description
Modified from 13752 - Mom, don't do that 2.0.
To further improve our security, we modify our encoding rule:
First, you'll be given a number n, and you'll use n to get a binary string Sn, following the representation:
S0 = "0"S1 = "1"Si = (Si-1) + ("1") + (reverse(invert(Si-1))) + ("0") + (invert(reverse(Si-2))) for i > 1
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, S2 is "11001", and S3 is "1100110110000".
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.
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.