Attack

时间限制:100s      空间限制:512MB

题目描述

  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,保证所有操作均合法。


题目来源

没有写明来源

Menuappsclose