为了测试他新买的绘图仪的功能，Byteasar 决定绘制一些“字节曲线”（bytecurves）。$n$ 阶字节曲线由 $2^n$ 条长度为 $\sqrt{2}$ 的线段组成。第一条线段连接坐标 $(0, 0)$ 和 $(1, 1)$ 的点。$n$ 阶字节曲线可以用一个长度为 $2^n-1$ 的、由字母 {L, R} 组成的字符串 $L_n$ 来描述。该字符串的第 $i$ 个字母表示在绘制完第 $i$ 条线段后，画笔转向并向左（字母 $\texttt{L}$）或向右（字母 $\texttt{R}$）垂直移动以绘制下一条线段。换句话说，画笔的方向会向左或向右改变 90°。

$L_1$ 由单个字母 L（左转）组成，$L_2$ 由三个字母 LLR 组成，表示两次左转后接一次右转。归纳地，$L_n$ 由 $L_{n-1}$ 生成：在 $L_{n-1}$ 的所有字母之间插入空格，并在 $L_{n-1}$ 的开头和结尾也各加一个空格。然后，在这些新产生的空格中，从 L 开始交替填入字母 L 和 R。例如，$L_3$ 的生成过程如下：$L_2 = \texttt{LLR} \to \texttt{LLR} \to \texttt{LLRLLRR} = L_3$。同理，$L_4 = \texttt{LLRLLRRLLLRRLRR}$（见下图）。

绘制字节曲线的一条线段需要整整一秒钟。在等待绘图仪完成打印时，Byteasar 思考了以下问题：给定平面上的一个点 $(x, y)$，画笔会在什么时候到达该点？例如，对于上图中 4 阶的字节曲线，画笔在绘图开始 7 秒后会到达点 $(-3, -1)$，并在 11 秒后再次到达该点。你的任务是回答 Byteasar 的问题。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 2\,000$)，其中 $n$ 表示字节曲线由 $L_n$ 描述，$m$ 表示有 $m$ 个查询点。接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($-10^9 \le x_i, y_i \le 10^9$)，表示第 $i$ 个查询点的坐标。注意，输入行中的坐标不一定代表字节曲线上的点。此外，输入文件中不会出现重复的点。

输出格式

输出包含 $m$ 行，对应各个查询的答案。每个答案包含一个非负整数 $k_i$，表示画笔访问查询点 $(x_i, y_i)$ 的次数；随后是 $k_i$ 个非负整数，按升序排列，表示访问该点的时刻（以绘图开始后的秒数为单位）。数字之间用单个空格分隔，行首和行尾不得有空格。

样例

输入

4 3
-3 -1
1 1
-1 0

输出

2 7 11
1 1
0