Attack

chnlich 非常喜欢玩《三国志》，并善于运用策略出奇制胜。现在，他即将踏上征服世界的旅途。

敌人拥有 $N$ 座城市和 $N$ 名太守。每座城市可以视为平面直角坐标系中的一个点，城市编号为 $0,1,2,\ldots,N-1$ 。编号为 $i$ 的城市坐标为 $(X_i,Y_i)$ ，镇守该城市的太守能力值为 $Z_i$ 。

每次行动时，chnlich 会选择一个边与坐标轴平行的矩形区域，并奇袭其中太守能力值第 $k$ 小的城市。奇袭结束后，城市和太守仍然存在。

为了防止弱点被发现，敌人有时会交换两座城市的太守。请你回答 chnlich 每次奇袭时所选太守的能力值。

输入格式

第一行包含两个整数 $N,M$ ，分别表示城市与太守的数量，以及接下来发生的事件数量。

接下来 $N$ 行，第 $i$ 行包含三个整数 $X_i,Y_i,Z_i$ ，表示编号为 $i$ 的城市坐标为 $(X_i,Y_i)$ ，其初始太守的能力值为 $Z_i$ 。其中城市编号从 $0$ 开始。

接下来 $M$ 行，每行描述一个事件，格式为以下两种之一：

QUERY x0 y0 x1 y1 k：询问以 $(x_0,y_0)$ 和 $(x_1,y_1)$ 为一对相对顶点的矩形区域中，太守能力值第 $k$ 小的能力值；
SWAP x y：交换编号为 $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 操作次数不超过 $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$ ，并保证所有操作均合法。

本题题面与测试数据整理自 BZOJ 2674。

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.