### 问题描述 小蓝最近在学矩阵，小桥作为他的好朋友，给了他一个挑战。 给定一个规模为 $n \times n$ 的矩阵 $a$，叫做带状矩阵，下标范围位 $1 \sim n$。 $a_{i,j}$ 表示从上往下数第 $i$ 行、从左往右数第 $j$ 列的元素，满足以下限制： 1. 当 $1\lt i \lt n$ 时，仅有 $a_{i,i-1},a_{i,i},a_{i,i+1}$ 为正值。 2. 当 $i=1$ 时，仅有 $a_{1,1},a_{1,2}$ 为正值。 3. 当 $i=n$ 时，仅有 $a_{n,n-1},a_{n,n}$ 为正整数。 4. 除了上述位置，其他位置都为 $0$。 具体排布如下： $$ \left[ \begin{matrix} a_{1,1} & a_{1,2} & 0 & 0 & 0 & \cdots & 0 & 0 \\\\ a_{2,1} & a_{2,2} & a_{2,3} & 0 & 0 & \cdots & 0 & 0 \\\\ 0 & a_{3,2} & a_{3,3} & a_{3,4} & 0 & \cdots & 0 & 0 \\\\ 0 & 0 & a_{4,3} & a_{4,4} & a_{4,4} & \cdots & 0 & 0 \\\\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\\\ 0 & 0 & 0 & 0 & 0 & \cdots & a_{n,n-1} & a_{n,n} \end{matrix} \right] $$ 小桥是计算机系的，他想要压缩这个矩阵。具体来说，由于很多位置都是 $0$，所以他想要一个一维数组来存储这个矩阵。 小桥的方案是：将 $0$ 值都抛弃，只存储整数，在一维数组 $b$ 中存储这些值，一位数组从下标 $0$ 开始。矩阵从第一行开始从左到右扫描，遇到正整数，就依次放到一维数组中，以次类推。 最后得到数组中的对应关系如下所示： $$ \begin{matrix} a_{1,1} & a_{1,2} & a_{2,1} & a_{2,2} & a_{2,3} & \cdots & a_{n,n-1} & a_{n,n} \\\\ \Updownarrow & \Updownarrow & \Updownarrow & \Updownarrow & \Updownarrow & \Updownarrow & \Updownarrow & \Updownarrow & \\\\ b_0 & b_1 & b_2 & b_3 & b_4 & \cdots & b_{3n-4} & b_{3n-3} \end{matrix} $$ 存储完成之后，需要满足一些询问要求，小桥会询问数组中的某个位置（从 $0$ 下标开始），然后你需要回答他该位置的值还原到矩阵中时，它的位置是多少，用两个整数 $(u,v)$ 表示它原来在矩阵中第 $u$ 行 $v$ 列。 小蓝一时间觉得十分麻烦，于是请你帮他解决这个问题。 ### 输入格式 第一行输入两个整数 $n, q$，代表矩阵的规模和询问的次数。 接下来 $q$ 行，每行一个整数 $x$，代表询问数组 $b$ 中下标为 $x$ 的位置的值还原到矩阵中的位置。 ### 输出格式 输出 $q$ 行，每行两个整数 $u,v$，用空格隔开，代表询问数组 $b$ 中下标为 $x$ 的位置的值还原到矩阵中是第 $u$ 行 $v$ 列。 ### 样例输入 ```bash 3 4 5 6 3 0 ``` ### 样例输出 ``` 3 2 3 3 2 2 1 1 ``` ### 说明 我们用 $b$ 数组表示压缩后一维数组的元素，还原到矩阵中就是： $$ \left[ \begin{matrix} a_{1,1} & a_{1,2} & 0 \\\\ a_{2,1} & a_{2,2} & a_{2,3} \\\\ 0 & a_{3,2} & a_{3,3} \end{matrix} \right] \Longleftrightarrow \left[ \begin{matrix} b_0 & b_1 & 0 \\\\ b_2 & b_3 & b_4 \\\\ 0 & b_5 & b_6 \end{matrix} \right] $$ ### 评测数据范围 $3 \le n \le 10^{12}, 1 \le q \le 10^5$。 保证询问的 $x$ 在一维数组中一定存在。