有$n$位阶梯进制，当$n=4$时，有：
$$
1={\begin{pmatrix}
0\\
0&0\\
0&0&0\\
0&0&0&1\\
\end{pmatrix}}\qquad
2={\begin{pmatrix}
0\\
0&0\\
0&0&0\\
0&0&1&0\\
\end{pmatrix}}\qquad
3={\begin{pmatrix}
0\\
0&0\\
0&0&0\\
0&0&1&1\\
\end{pmatrix}}\\
4={\begin{pmatrix}
0\\
0&0\\
0&0&1\\
0&0&1&0\\
\end{pmatrix}}\qquad
5={\begin{pmatrix}
0\\
0&0\\
0&0&1\\
0&0&1&1\\
\end{pmatrix}}\qquad
6={\begin{pmatrix}
0\\
0&0\\
0&0&0\\
0&1&0&0\\
\end{pmatrix}}\\
18={\begin{pmatrix}
0\\
0&1\\
0&1&0\\
0&1&0&0\\
\end{pmatrix}}\\
\,\,\,\quad\quad\quad\quad{\color{red} 4}\quad{\color{red} 3}\quad{\color{red} 2}\quad{\color{red} 1}\quad\it{\color{red} {第i\,阶}}
$$
阶梯进制的由来：
众所周知，小包包是个帅哥，并且十分追求完美，是个完美主义者。他善于思考，并且想把一切不美好的事物变得更加美好。大家都知道，一个十进制数转换成$n$位二进制数将变成一串长度为$n$的$01$串，例如当$n=8$时，有：
$$
(2)_{10}=(00000010)_2\\
(127)_{10}=(01111111)_2
$$
小包包很早以前就觉得一长串$0$和$1$太不美观，一直希望能改变它，希望寄予天天向上的积极思想，因此小包包创造了一个由$0$和$1$组成的阶梯进制，它由$n$阶组成（由$1$阶到$n$阶逐级上升）。它遵循以下几条规则：
1. 当第$1$阶为$0$，该数加$1$时，第$1$阶置为$1$。
2. 每当第$i$（$i\geq 2$）阶的低阶（即第$i-1$阶）全为$1$，第$i-1$阶再获得$1$时，第$i-1$阶所有的$1$会置为$0$，并会向第$i$阶进$1$。
3. 所有$1$下方不会有$0$。（因为小包包认为该进制数寓意着人生，从低阶一步步加油努力，每一阶代表人生的一个阶段，因为踏踏实实走好每一步，所以基础很牢固，$1$就象征着那份努力，同学们也要像小包包一样好好学习呀！）
据说将若干个十进制数转换成该阶梯进制，就能获得小包包的嘉奖，来挑战一下吧！
多组输入。
每组输入$n$和$m$。($1\leq n\leq 18$, $1\leq m\leq 1000$)
接下来$m$行，每行有一个十进制数$a$。($0\leq a\leq2^{63}-1$)