Йо-хо-хо, и бутылка рома.
Пей, и дьявол тебя доведет до конца.
Йо-хо-хо, и бутылка рома.
В трактир «Адмирал Бенбоу» привезли новую партию рома — всего $$$2^{n} - 1$$$ бутылок, и каждая из них имеет свой номер от 1 до $$$2^{n} - 1$$$. Кроме того, в трактире есть $$$2^{n} - 1$$$ коробок, также пронумерованных от $$$1$$$ до $$$2^{n} - 1$$$.
Джимми Гоккинс хочет разложить все бутылки рома по коробкам, при этом соблюдая необычное правило: если он кладет бутылку с номером $$$k$$$ в коробку с тем же номером $$$k$$$, то появляется дополнительная бутылка, чей номер равен количеству единиц в двоичной записи числа $$$k$$$. Однако если это количество единиц совпадает с самим $$$k$$$, то новая бутылка не появляется.
Джимми решил, что будет класть бутылку с номером $$$k$$$ только в коробку с номером $$$k$$$. Также ему стало интересно, сколько бутылок рома окажется в каждой из коробок с номерами $$$a_i$$$. Помогите Джимми узнать ответ!
В первой строке вводится целое число $$$n$$$ $$$(1 \leq n \leq 60)$$$.
Во второй строке вводится целое число $$$q$$$ — количество коробок, которые интересуют Джимми $$$(1 \leq q \leq 10 ^ 5)$$$.
В следующей строке идут $$$q$$$ целых чисел $$$a_i$$$ — номера коробок, которые интересны Джимми $$$(1 \leq i \leq q, 1 \leq a_i \leq 2 ^ n - 1)$$$.
Выведите в одной строке $$$q$$$ чисел — количество бутылок рома в коробках с номерами $$$a_i$$$.
5 2 8 4
1 6
В коробку с номером $$$8$$$ попадёт одна бутылка из начального набора. В коробку с номером $$$4$$$ также попадёт бутылка из начального набора и еще пять дополнительных, полученных из коробок с номерами: $$$30=11110_2$$$, $$$29=11101_2$$$, $$$27=11011_2$$$, $$$23=10111_2$$$, $$$15=1111_2$$$
