Bajtocji 的居民最近流行起一种名为“希尔伯特台球”（bilard Hilberta）的原创游戏。

该游戏的台球桌尺寸为 $2^{n+1} \times 2^{n+1}$，我们将数字 $n$ 称为台球桌的阶数。桌面上放置了构成 $n$ 阶希尔伯特曲线的隔板。下图展示了 $n = 1, 2, 3$ 时的台球桌。

台球桌的左下角坐标为 $(0, 0)$，右下角坐标为 $(2^{n+1}, 0)$，右上角坐标为 $(2^{n+1}, 2^{n+1})$。左图展示了 $n=1$ 阶希尔伯特曲线构成的隔板。对于 $n \ge 2$，构成 $n$ 阶台球桌隔板的希尔伯特曲线由四个 $n-1$ 阶的曲线组成，分别位于台球桌的四个象限中，并由三条长度为 $2$ 的额外隔板连接（见图）。左下角的曲线顺时针旋转了 $90^\circ$，而右下角的曲线逆时针旋转了 $90^\circ$。

一颗台球从坐标 $(1, 0)$ 出发，初始速度向量为 $(1, 1)$。在运动过程中，台球会与构成希尔伯特曲线的隔板以及台球桌的边缘发生理想弹性碰撞。为简化起见，假设台球的大小可以忽略不计。请确定台球在 $t$ 个单位时间后所在的位置坐标。图中用红色标出了 $n=3$ 时台球轨迹的起点；例如，在 $t=42$ 个单位时间后，台球将位于坐标 $(3, 14)$ 处。

输入格式

输入的第一行包含两个整数 $n$ 和 $z$ ($1 \le n \le 30, 1 \le z \le 100\,000$)，分别表示台球桌的阶数和查询次数。

接下来的 $z$ 行按递增顺序包含查询：第 $i$ 行包含一个整数 $t_i$，表示第 $i$ 次查询的时间单位数 ($0 < t_1 < t_2 < \dots < t_z < 2^{2(n+1)}$)。

输出格式

输出应包含恰好 $z$ 行，作为对输入查询的回答：第 $i$ 行应包含两个由空格分隔的整数，表示台球在 $t_i$ 个单位时间后所在位置的坐标。

样例

输入 1

3 2
1
42

输出 1

2 1
3 14