题目描述

美术课上，同学们在一张 $n$ 行 $m$ 列的方格纸上按顺时针螺旋的顺序依次写数：从左上角（第 $1$ 行第 $1$ 列）开始写 $1$，先向右写，碰到边界或者已经写过数的格子就向右转（右 → 下 → 左 → 上 → 右……），直到写满 $1 \sim n \times m$ 为止。

例如 $n = 3, m = 4$ 时，写出来是：

 1  2  3  4
10 11 12  5
 9  8  7  6

老师会提出 $q$ 个问题，问题有两种：

• 1 k：数 $k$ 写在第几行第几列？
• 2 x y：第 $x$ 行第 $y$ 列写的是哪个数？

请你回答所有问题。

输入格式

第一行三个整数 $n, m, q$。

接下来 $q$ 行，每行一个问题，格式为 1 k 或 2 x y。

输出格式

对于每个问题输出一行：

• 问题 1 k：输出两个整数，表示所在的行号和列号，中间用一个空格隔开；
• 问题 2 x y：输出一个整数，表示该格中写的数。

样例 #1

样例输入 #1

3 4 4
1 12
2 3 1
1 6
2 2 2

样例输出 #1

2 3
9
3 4
11

样例解释

方格纸如题目描述中所示。$12$ 在第 $2$ 行第 $3$ 列；第 $3$ 行第 $1$ 列是 $9$；$6$ 在第 $3$ 行第 $4$ 列；第 $2$ 行第 $2$ 列是 $11$。

提示

数据范围

• 对于 $30\%$ 的数据：$n, m \le 10$；
• 对于 $60\%$ 的数据：$n, m \le 100$，$q \le 100$；
• 对于 $100\%$ 的数据：$1 \le n, m \le 1000$，$1 \le q \le 10^5$，$1 \le k \le n \times m$，$1 \le x \le n$，$1 \le y \le m$。

提示

• 用二维数组 a[x][y] 模拟写数的过程，可以写一个函数专门负责填数。用两个方向数组 dx[4]、dy[4] 表示右、下、左、上四个方向，「向右转」就是方向编号加 $1$ 再对 $4$ 取余。
• 判断能否继续前进：下一格不能越界，也不能已经写过数（初始全为 $0$）。
• 对于问题 1，如果每次都在整个二维数组里查找会超时。可以在填数的同时，用两个一维数组记下每个数所在的行和列。
• 二维数组较大时，应定义成全局变量。