Attack

提交提交记录讨论

　　chnlich非常喜欢玩三国志这款游戏，并喜欢用一些策略出奇制胜。现在，他要开始征服世界的旅途了。
　　他的敌人有N座城市和N个太守，N个城市可以看作在二维平面上的N个点。
　　N座城市的标号为0,1,2,……,N-1。
　　第i座城市的坐标为(Xi,Yi)，镇守这座城市的太守的能力值为Zi。
　　chnlich每次会选择一个边平行于坐标轴的矩形区域，并奇袭其中太守能力值第K小的城市(奇袭结束之后城市与太守依然存在)。
　　不过，他的敌人经常会偷偷交换两座城市的太守，防止弱点被chnlich发现。
　　现在，chnlich想要知道，每次奇袭时他的敌人的能力值。

　　输入的第一行包含两个整数N,M，N表示城市与太守的个数，M表示接下来发生了M个事件。
　　输入的第二行到第N+1行，每行包含三个整数，第i+2行的三个整数依次表示编号为i的城市的Xi,Yi,Zi，含义如题所述。
　　输入的第N+2行到第N+M+1行，每行有两种可能形式：
　　第一种
　　QUERY x0 y0 x1 y1 k
　　表示chnlich询问一个相对顶点为(x0,y0),(x1,y1)的矩形中，第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<=1000;

　　对于40%的数据，N<=30000;

　　另有10%的数据，不存在SWAP操作;

　　另有10%的数据，QUERY操作次数<=2;

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

　　对于100%的数据，N<=60000,M<=10000,0<=Xi,Yi,Zi<=10^9,k<=10^9，保证所有操作均合法。

#2674. Attack

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示