#P4848. 崂山白花蛇草水

崂山白花蛇草水

题目描述

神犇 Aleph 在 SDOI Round2 前立了一个 flag:如果进了省队,就现场直播喝崂山白花蛇草水。凭借着神犇 Aleph 的实力,他轻松地进了山东省省队,现在便是他履行诺言的时候了。蒟蒻 Bob 特地为他准备了 999,999,999,999,999,999 瓶崂山白花蛇草水,想要灌神犇 Aleph。神犇 Aleph 求(跪着的)蒟蒻 Bob 不要灌他,由于神犇 Aleph 是神犇,蒟蒻 Bob 最终答应了他的请求,但蒟蒻 Bob 决定将计就计,也让神犇 Aleph 回答一些问题。

具体说来,蒟蒻 Bob 会在一个宽敞的广场上放置一些崂山白花蛇草水(可视为二维平面上的一些整点),然后询问神犇 Aleph 在矩形区域 x1xx2,y1yy2x_1\le x\le x_2,y_1\le y\le y_2 中,崂山白花蛇草水瓶数第 kk 多的是多少。为了避免麻烦,蒟蒻 Bob 不会在同一个位置放置两次或两次以上的崂山白花蛇草水,但蒟蒻 Bob 想为难一下神犇 Aleph,希望他能在每次询问时立刻回 答出答案。

神犇 Aleph 不屑于做这种问题,所以把这个问题交给了你。

输入格式

输入的第一行为两个正整数 nnqq,表示横纵坐标的范围和蒟蒻 Bob 的操作次数(包括放置次数和询问次数)。

接下来 qq 行,每行代表蒟蒻 Bob 的一个操作,操作格式如下:
首先第一个数字 type\mathrm{type},表示操作种类。type=1\mathrm{type}=1 表示放置,type=2\mathrm{type}=2 表示询问。
type=1\mathrm{type}=1,接下来会有三个正整数 x,y,vx, y, v,表示在坐标整点 (x,y)(x, y) 放置v瓶崂山白花蛇草水。
type=2\mathrm{type}=2,接下来会有五个正整数 x1,y1,x2,y2,kx_1, y_1, x_2, y_2, k,表示询问矩形区域 x1xx2,y1yy2x_1\le x\le x_2,y_1\le y\le y_2 中,崂山白花蛇草水瓶数第 kk 多的是多少。

为了体现程序的在线性,你需要将每次读入的数据(除了 type\mathrm{type} 值)都异或 lastans\mathrm{lastans},其中 lastans\mathrm{lastans} 表示上次询问的答 案。如果上次询问的答案为 NAIVE!ORZzyz.(见样例输出),则将 lastans\mathrm{lastans} 置为 00。初始时的 lastans\mathrm{lastans}00。 初始时平面上不存在崂山白花蛇草水。

输出格式

对于每个 type=2\mathrm{type}=2 的操作,一行输出崂山白花蛇草水瓶数第 kk 多的是多少。若不存在第 kk 多的瓶数, 请输出 NAIVE!ORZzyz.

10 7
1 1 1 1
1 2 2 3
1 4 1 2
1 3 4 4
2 1 1 4 1 3
2 2 2 3 5 4
2 2 1 4 4 2
NAIVE!ORZzyz.
NAIVE!ORZzyz.
3

提示

对于所有数据,n500000n\le500000q100000q\le1000001x,yn1\le x, y\le n1v1091\le v\le 10^91x1x2n1\le x_1\le x_2\le n1y1y2n1\le y_1\le y_2\le n1kq1\le k\le q