题目描述

平面上有一列信标 $P_1,P_2,P_3,\dots$，其中 $P_1=(1,0)$。 从 $P_i$ 走到 $P_{i+1}$ 时，移动方向依次按照「上、左、下、右」循环； 移动距离依次为：$1,2,2,3,3,4,4,\dots$。

因此前几个信标为：

$$P_1=(1,0),\ P_2=(1,1),\ P_3=(-1,1),\ P_4=(-1,-1),\ P_5=(2,-1),\dots $$

需要回答 $q$ 次询问，询问有两种：

1. 1 n：求信标 $P_n$ 的坐标；
2. 2 l r：求折线 $P_lP_{l+1}\cdots P_r$ 的长度。

输入格式

第一行输入一个整数 $q$，表示询问数量。 接下来 $q$ 行，每行输入一条询问。

输出格式

每条询问输出一行。

• 对于第一类询问：输出两个整数，表示 $P_n$ 的横坐标、纵坐标。
• 对于第二类询问：输出一个整数，表示所求折线的长度。

样例输入 #1

3
1 9
2 1 9
1 2020

样例输出 #1

3 -2
24
-505 -505

样例解释：$P_9=(3,-2)$，从 $P_1$ 沿折线走到 $P_9$ 的路程为 $24$。

数据范围

对于全部数据： $1 \le q \le 10^5$。 第一类询问满足 $1 \le n \le 10^9$； 第二类询问满足 $1 \le l<r \le 10^6$。

共20个测试点，每个测试点5分。