Personal Contest 2010.07.20 (public)

From: 2010-07-20 12:00:00 To: 2010-07-20 15:00:00 Now: 2017-09-22 06:54:19 Status: Public

A - 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