题目描述

小 $\verb!X!$ 正在学习平面直角坐标系，他遇到了一道难题：

现给出一个平面直角坐标系 $xOy$，有点 $A_1(1,0),A_2(1,1),A_3(−1,1),A_4(−1,−1),A_5(2,−1),...$。

有两种询问：

• 形如 1 n，表示询问点 $A_n$ 的坐标。
• 形如 2 l r，表示询问折线段 $A_{l}A_{l+1}A_{l+2}...A_{r-1}A_{r}$ 的长度。

输入格式

第一行一个整数 $q$，表示有 $q$ 次询问。

接下来 $q$ 行，每行一次询问。

输出格式

对于每次询问，输出对应的值。

样例 #1

3
1 9
2 1 9
1 2020

3 -2
24
-505 -505

样例解释 #1

• 对于询问 $1$，有 $A_9(3,-2)$。
• 对于询问 $2$，折线段长度为 $A_1A_2 + A_2A_3 + \cdots + A_8A_9 = 24$。

样例 #2

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

10
2 2
-1 -1
-2 2
-1 1
2 2
4
26
16

提示

特殊性质 $A$:仅包含询问 $1$。

对于 $100\%$ 的数据，都有 $1 \leq n \leq 10^9$，$1 \leq l < r \leq 10^6$，$1 \leq q \leq 10^5$。