P14255 列车（train）

洛咕咕王国是咕咕星球上领土最辽阔的王国，因此在洛咕咕王国中如何高效移动成为了一个难题。洛咕咕王国有 $n$ 座城市，神奇的是这 $n$ 座城市在一条直线上，我们把第 $i$ 座城市在直线上的位置记作 $p_i$。这些城市是按照顺序进行编号的， 因此 $p_1

**本题包含多组测试数据。** 第一行包含一个正整数 $T$，表示数据组数。 接下来包含 $T$ 组数据，每组数据的格式如下： - 第一行包含两个正整数 $n,m$，表示城市个数和事件次数。 - 第二行包含 $n$ 个正整数 $p_1,p_2,\dots,p_n$，表示各个城市在直线上的位置。 - 接下来 $m$ 行每行表示一次事件的发生。首先读入一个正整数 $o$ 表示事件类型： - 若 $o=1$ 表示发生了一个类型 1 事件，接下来两个正整数 $x_i,y_i$ 表示停开所有起点站城市编号大于等于 $x_i$ **且**终点站编号小于等于 $y_i$ 的列车。 - 若 $o=2$ 表示发生了一个类型 2 事件，接下来两个正整数 $x_i,y_i$ 表示查询搭乘一趟未停开列车从城市 $x_i$ 搭乘至城市 $y_i$ 的最小花费。

对于每组数据：输出若干行，对于每个类型 2 事件输出一行一个整数表示答案：若存在对应的列车可以搭乘则输出最小花费，否则输出 `-1`。

**【样例 1 解释】** 在第一组测试数据中，最初共有 $6$ 趟列车开行。 - 第 $1$ 个事件：查询从城市 $1$ 搭乘至城市 $3$ 的最小花费。当前所有列车均在开行，因此最优的方案是搭乘以城市 $1$ 为起点站、城市 $3$ 为终点站的列车，花费为 $p_3-p_1=3-1=2$。 - 第 $2$ 个事件：查询从城市 $3$ 搭乘至城市 $4$ 的最小花费。当前所有列车均在开行，因此最优的方案是搭乘以城市 $3$ 为起点站、城市 $4$ 为终点站的列车，花费为 $p_4-p_3=4-3=1$。 - 第 $3$ 个事件：停开所有起点站城市编号大于等于 $2$，终点站城市编号小于等于 $3$ 的列车，即停开以城市 $2$ 为起点站、城市 $3$ 为终点站的列车。 - 第 $4$ 个事件：查询从城市 $2$ 搭乘至城市 $3$ 的最小花费。由于以城市 $2$ 为起点站、城市 $3$ 为终点站的列车已被停开，所以**无法搭乘这趟列车**。最优方案之一是搭乘以城市 $1$ 为起点站、城市 $3$ 为终点站的列车，花费为 $p_3-p_1=3-1=2$，可以证明不存在花费更小的方案。 - 第 $5$ 个事件：停开所有起点站城市编号大于等于 $1$，终点站城市编号小于等于 $4$ 的列车，即停开所有列车。以城市 $2$ 为起点站、城市 $3$ 为终点站的列车先前已被停开，本次事件将不会对这趟列车产生任何影响。 - 第 $6$ 个事件：查询从城市 $1$ 搭乘至城市 $4$ 的最小花费。由于所有列车已被停开，无法从城市 $1$ 搭乘至城市 $4$ ，故输出 `-1`。 对于第二组测试数据，我有一个绝佳的解释，但是这里空间太小写不下。 **【样例 2】** 见选手目录下的 `train/train2.in` 与 `train/train2.ans`。 该组样例满足测试点 $1$ 的限制。 **【样例 3】** 见选手目录下的 `train/train3.in` 与 `train/train3.ans`。 该组样例满足测试点 $4$ 的限制。 **【样例 4】** 见选手目录下的 `train/train4.in` 与 `train/train4.ans`。 该组样例满足测试点 $8$ 的限制。 **【样例 5】** 见选手目录下的 `train/train5.in` 与 `train/train5.ans`。 该组样例满足测试点 $11$ 的限制。 **【样例 6】** 见选手目录下的 `train/train6.in` 与 `train/train6.ans`。 该组样例满足测试点 $13$ 的限制。 **【样例 7】** 见选手目录下的 `train/train7.in` 与 `train/train7.ans`。 该组样例满足测试点 $15$ 的限制。 **【样例 8】** 见选手目录下的 `train/train8.in` 与 `train/train8.ans`。 该组样例满足测试点 $19$ 的限制。 **【样例 9】** 见选手目录下的 `train/train9.in` 与 `train/train9.ans`。 该组样例满足测试点 $23$ 的限制。 **【数据范围】** 对于所有测试数据，保证：$1\leq T\leq 10$，$2\leq n,m\leq 10^5$，$1\leq x