1382 - Sort the binary

Time Limit: 1s Memory Limit: 128MB

Submissions: 241 Solved: 100
Description

sort a sequence 1,2,3,...,n as the rule below:
1. the binary of the number has fewer '1' stand in front.
2. if tile just put the smaller one in front.
give you a number k, tell me it's position (count from 1) in the sequence.(1<=k<=n<=1000000)

Input

The first line is n.
The second line is q indicate q questions.(q<=n)
next q lines, each one is the question about the position of the number.

Output

output q lines, each line is a position.

Sample Input
8
4
1
3
4
8
Sample Output
1
5
3
4
Hint

For the case, after sort, the sequence is 1 2 4 8 3 5 6 7

Source
Zehua HONG