题目描述

chnlich 非常喜欢玩三国志这款游戏，并喜欢用一些策略出奇制胜。现在，他要开始征服世界的旅途了。

他的敌人有 $N$ 座城市和 $N$ 个太守，N个城市可以看作在二维平面上的 $N$ 个点。$N$ 座城市的标号为$0,1,2,\dots,N-1$。第 $i$ 座城市的坐标为 $(X_i,Y_i)$，镇守这座城市的太守的能力值为 $Z_i$。 chnlich 每次会选择一个边平行于坐标轴的矩形区域，并奇袭其中太守能力值第 $K$ 小的城市（奇袭结束之后城市与太守依然存在）。不过，他的敌人经常会偷偷交换两座城市的太守，防止弱点被 chnlich 发现。

现在，chnlich 想要知道，每次奇袭时他的敌人的能力值。

输入格式

输入的第一行包含两个整数 $N,M$，$N$ 表示城市与太守的个数，$M$ 表示接下来发生了 $M$ 个事件。

输入的第二行到第 $N+1$ 行，每行包含三个整数，第 $i+2$ 行的三个整数依次表示编号为i的城市的 $X_i,Y_i,Z_i$，含义如题所述。

输入的第 $N+2$ 行到第 $N+M+1$ 行，每行有两种可能形式：

-第一种 QUERY x0 y0 x1 y1 k 表示 chnlich 询问一个相对顶点为 $(x_0,y_0),(x_1,y_1)$ 的矩形中，第 $k$ 小能力值太守的能力值。

• 第二种 SWAP x y 表示 chnlich 的敌人交换了编号为 $x$ 和 $y$ 两座城市的太守。

输出格式

对于每一个 QUERY，输出一行。若不存在第 $k$ 小能力值的太守，输出 It doesn't exist.。否则输出一个整数，表示矩形内能力值第 $k$ 小太守的能力值。

样例输入

3 5
1 1 1
2 2 2
3 3 3
QUERY 1 1 3 3 3
SWAP 0 1
QUERY 2 2 4 4 1
SWAP 2 2
QUERY 2 2 3 3 3

样例输出

3
1
It doesn't exist.

数据规模与约定

对于 $30\%$ 的数据，$N,M\le 10^3$。

对于 $40\%$ 的数据，$N\le 3\times 10^4$。

另有 $10\%$ 的数据，不存在 SWAP 操作。

另有 $10\%$ 的数据，QUERY 操作次数 $\le 2$。

另有 $10\%$ 的数据，所有城市的 $Y$坐标都相等，且询问中矩形的 $Y$ 坐标与所有城市的 $Y$ 坐标均相等;

对于 $100\%$ 的数据，$N\le 6\times 10^4,M\le 10^4,0\le X_i,Y_i,Z_i\le 10^9,k\le 10^9$，保证所有操作均合法。