题目描述

幻方是中国传统数学游戏,旧时在官府、学堂多见。它是将从$1$到$n^2$的自然数排成纵横各为$n$的正方形矩阵,使在同一行、同一列和同一对角线上的几个数的和都相等,这类正方形矩阵被称为$n$阶幻方。

juezhi发现了这个游戏,觉得很有意思。经过祂的研究,发现了一种奇数阶幻方构造方法,有口诀如下:
一居上行正中央,依次斜填切莫忘
上出框界往下写,右出框时左边放
重复便在下格填,右上重复一个样

这个口诀的解释如下:
将数字1放在第一行正中间的位置,每一个数放在前一个数的右上一格
如果这个数所要放的格已经超出了顶行那么就把它放在底行,仍然要放在右一列
如果这个数所要放的格已经超出了最右列那么就把它放在最左列,仍然要放在上一行
如果这个数所要放的格已经超出了顶行且超出了最右列或者该格子已经有数填入,那么就把它放在前一个数的下一行同一列的格内
以下是按照这种方法完成的三阶幻方和五阶幻方:

现在juezhi想考考你,以某奇数 $d$ 作为阶数,由这种方式构造出来的幻方的第x行第y列的数字num,以及数字k出现在哪行哪列?

询问一:给出阶数$d$、行数$x$和列数$y$ $(1 \le d \le 1e9, 1 \le x, y \le d)$,问该位置的数字是几?

询问二:给出阶数$d$和数字$x$ $(1 \le d \le 1e9, 1 \le x \le d^2)$,问数字$x$在哪行哪列?

题目数据保证$d$为奇数


输入格式

每轮测试有多轮测试样例。第一行包括一个数字$p$,$q$($1 \le p \le 100000, 1 \le q \le 100000$)。------表示有$p$组询问一和$q$组询问二,接下来分别给出询问一和询问二。
对于每个询问一,给出一行三个数字$d, x, y(1 \le d \le 1e9, 1 \le x, y \le d)$。
对于每个询问二,给出一行两个数字$d, x(1 \le d \le 1e9, 1 \le x \le d^2)$。


输出格式

输出$p+q$行答案。对于每个询问一,输出一行一个数字。对于每个询问二,输出一行两个数字,中间用空格隔开。详情可见样例。


样例数据

输入

### 输入样例一
4 4
1 1 1
3 2 2
5 3 5
5 2 3
1 1
3 3
5 20
5 25

### 输入样例二
1 1
999999999 999999999 999999999
999999999 123456789

输出

### 输出样例一
1
5
22
7
1 1
2 1
3 4
5 3

### 输出样例二
499999998500000000
876543212 623456788


备注


操作

评测记录

优秀代码

信息

时间限制: 2s
内存限制: 128MB
评测模式: Normal

题解