В трактир «Адмирал Бенбоу» привезли новую партию рома — всего 2ⁿ − 1 бутылок, и каждая из них имеет свой номер от 1 до 2ⁿ − 1. Кроме того, в трактире есть 2ⁿ − 1 коробок, также пронумерованных от 1 до 2ⁿ − 1.

Джимми Гоккинс хочет разложить все бутылки рома по коробкам, при этом соблюдая необычное правило: если он кладет бутылку с номером k в коробку с тем же номером k, то появляется дополнительная бутылка, чей номер равен количеству единиц в двоичной записи числа k. Однако если это количество единиц совпадает с самим k, то новая бутылка не появляется.

Джимми решил, что будет класть бутылку с номером k только в коробку с номером k. Также ему стало интересно, сколько бутылок рома окажется в каждой из коробок с номерами a_i. Помогите Джимми узнать ответ!

В первой строке вводится целое число n (1 ≤ n ≤ 60).

Во второй строке вводится целое число q — количество коробок, которые интересуют Джимми (1 ≤ q ≤ 10 5).

В следующей строке идут q целых чисел a_i — номера коробок, которые интересны Джимми (1 ≤ i ≤ q, 1 ≤ a_i ≤ 2 n − 1).

Выведите в одной строке q чисел — количество бутылок рома в коробках с номерами a_i.

В коробку с номером 8 попадёт одна бутылка из начального набора. В коробку с номером 4 также попадёт бутылка из начального набора и еще пять дополнительных, полученных из коробок с номерами: 30=11110₂, 29=11101₂, 27=11011₂, 23=10111₂, 15=1111₂