题目描述

从前，在 Burlyandia 王国，公主 Burenka 想取悦她的朋友 ReLu。考虑到 ReLu 对加密货币也有兴趣，Burenka 决定创建自己的区块链加密货币，命名为 Pether。

在修读了网络安全相关课程并接受专家指导后，Burenka 决定让 Pether 得到尽可能好的保护。因此，设置了极其复杂的限制条件，并非所有用户之间都能相互兑换 Pether。

Pether 区块链的结构十分复杂。所有用户用整数 $1$ 到 $n$ 编号，每个用户被分配了唯一的标识符 $a_i$，同时货币有一个安全参数 $d$。

用户 $i$ 仅在满足 $i < j$ 且 $a_i < a_j$ 时，才能直接向用户 $j$ 转账 Pether。但这还不够！

用户间的直接转账需通过一系列中间交易完成。每笔交易中，后续每个中间用户（包括最后一个用户 $j$）的标识符必须严格递增，且增幅不超过 $d$。此外，除起点 $i$ 和终点 $j$ 外，所有中间用户的标识符都必须严格小于 $a_i$。

更形式化地说，用户 $i$ 能直接向用户 $j$ 转账的条件如下：

1. 满足 $i < j$；
2. 满足 $a_i < a_j$；
3. 存在长度为 $k$ 的中间用户序列 $x$，使得： (a) $i = x_1 < x_2 < \dots < x_{k-1} < x_k = j$； (b) 对于所有 $1 \le t \le k-1$，有 $x_{t+1} - x_t \le d$； (c) 对于所有 $2 \le t \le k-1$，有 $a_{x_t} < a_i$。

Burenka 请你作为她的专业程序员，理解这套系统，并回答若干组用户间转账的查询。

每个查询需要你判断：是否存在一条直接转账序列（可经过中间用户），允许从用户 $u_i$ 向用户 $v_i$ 转账 Pether。

• 若 $t_i = 1$，仅需判断是否可行；
• 若 $t_i = 2$，还需最小化直接转账的次数（转账过程中直接转账的总次数需达到最小）。

输入格式

第一行包含三个整数 $n, d, g$（$1 \le n, d \le 300000$，$0 \le g \le 12$），分别表示用户数量、安全参数、测试组编号。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），表示每个用户的标识符，保证所有 $a_i$ 互不相同。

第三行包含一个整数 $q$（$1 \le q \le 300000$），表示查询数量。

接下来 $q$ 行，每行包含三个整数 $t_i, u_i, v_i$（$t_i \in \{1,2\}$，$1 \le u_i < v_i \le n$）：

• $u_i$ 为转账发起方，$v_i$ 为接收方；
• $t_i=1$：判断是否可行；
• $t_i=2$：判断可行且输出最少直接转账次数。

输出格式

输出 $q$ 行，第 $i$ 行对应第 $i$ 个查询的答案：

• 若无法转账，输出 $0$；
• 若 $t_i=1$，可行则输出 $1$；
• 若 $t_i=2$，可行则输出最少直接转账次数。

6 1 0
2 1 34 5 6
6
2 1 3
2 1 2
1 1 4
2 1 5
2 1 6
1 2 6

1
0
1
3
4
1

6 2 0
1 2 34 5 6
6
2 1 5
2 2 5
2 1 6
2 2 6
2 1 4
2 2 4

2
2
3
2
2
1

10 2 0
2 1 43 5 6 8 710 9
10
2 1 5
1 2 5
2 3 5
2 1 9
2 5 8
2 3 9
2 1 8
1 1 2
2 3 8
2 1 9

2
1
1
4
2
3
3
0
2
4

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 10^7$。