题目背景

译自 Potyczki Algorytmiczne 2016 R5 Bilard Hilberta [A] (HIL)。

题目描述

考虑如下的 Hilbert 曲线：

$n$ 阶的 Hilbert 曲线的大小为 $2^{n+1}\times 2^{n+1}$。这里，$n\ge 1$。

$n=1$ 时的曲线在下图中给出，而 $n\gt 1$ 时的曲线由四个 $(n-1)$ 阶的曲线组成。左下角的曲线被顺时针旋转了 $90^\circ$，而右下角的曲线则被逆时针旋转了 $90^\circ$，而且在左上与左下、左上与右上、右上与右下的曲线的相接处添加了长度为 $2$ 的额外曲线将它们连为一体。

下图中从左至右分别展示了 $n=1,2,3$ 时的曲线。

令左下角的坐标为 $(0,0)$，右下角的坐标为 $(2^{n+1},0)$，右上角坐标为 $(2^{n+1},2^{n+1})$。

将球视为质点。球从 $(1,0)$ 出发，其速度矢量 $\boldsymbol{v}=(1,1)$。撞到边缘或者曲线上之后，它会反弹，这里的碰撞是完全弹性碰撞，也就是垂直于撞击面的速度分量反向，平行于撞击面的速度分量不变。可以证明撞到的一定是一个面，没有撞到角的情况。

$m$ 次询问，每次问球出发 $t_i$ 秒后，球的位置。

输入格式

第一行两个正整数 $n,m$。

接下来 $m$ 行，第 $i$ 行只有一个整数 $t_i$，描述一次询问。

输出格式

输出 $m$ 行，每行两个整数表示球的位置。

3 2
1
42

2 1
3 14

提示

样例解释

在【题目描述】的图中已经给出。

数据范围

• $1\le n\le 30$；
• $1\le m\le 10^5$；
• $0\lt t_1\lt t_2\lt \ldots \lt t_m\lt 2^{2(n+1)}$。