8605: BZOJ4605：崂山白花蛇草水

神犇Aleph在SDOI Round2前立了一个flag：如果进了省队，就现场直播喝崂山白花蛇草水。凭借着神犇Aleph的实 力，他轻松地进了山东省省队，现在便是他履行诺言的时候了。蒟蒻Bob特地为他准备了999,999,999,999,999,999 瓶崂山白花蛇草水，想要灌神犇Aleph。神犇Aleph求（跪着的）蒟蒻Bob不要灌他，由于神犇Aleph是神犇，蒟蒻Bo b最终答应了他的请求，但蒟蒻Bob决定将计就计，也让神犇Aleph回答一些问题。具体说来，蒟蒻Bob会在一个宽敞 的广场上放置一些崂山白花蛇草水（可视为二维平面上的一些整点），然后询问神犇Aleph在矩形区域(x1, y1), ( x2, y2)(x1≤x2且y1≤y2，包括边界)中，崂山白花蛇草水瓶数第k多的是多少。为了避免麻烦，蒟蒻Bob不会在同 一个位置放置两次或两次以上的崂山白花蛇草水，但蒟蒻Bob想为难一下神犇Aleph，希望他能在每次询问时立刻回 答出答案。神犇Aleph不屑于做这种问题，所以把这个问题交给了你。

输入格式

输入的第一行为两个正整数N, Q，表示横纵坐标的范围和蒟蒻Bob的操作次数（包括放置次数和询问次数）。 接下来Q行，每行代表蒟蒻Bob的一个操作，操作格式如下： 首先第一个数字type，表示操作种类。type=1表示放置，type=2表示询问。 若type=1，接下来会有三个正整数x, y, v，表示在坐标整点(x, y)放置v瓶崂山白花蛇草水。(1≤x, y≤N, 1≤v≤10^9) 若type=2，接下来会有五个正整数x1, y1, x2, y2, k，表示询问矩形区域(x1, y1), (x2, y2)中，崂山白花蛇草水瓶数第k多的是多少。 (1≤x1≤x2≤N，1≤y1≤y2≤N，1≤k≤Q) 为了体现程序的在线性，你需要将每次读入的数据（除了type值）都异或lastans，其中lastans表示上次询问的答 案。如果上次询问的答案为"NAIVE!ORZzyz."（见样例输出），则将lastans置为0。初始时的lastans为0。 初始时平面上不存在崂山白花蛇草水。 本题共有12组测试数据。对于所有的数据，N≤500,000。 Q的范围见下表： 测试点1-2     Q=1,000 测试点3-7     Q=50,000 测试点8-12     Q=100,000

输出格式

对于每个询问(type=2的操作)，回答崂山白花蛇草水瓶数第k多的是多少。若不存在第k多的瓶数， 请输出"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

提示

没有写明提示

题目来源

Idea By Aleph, Description & Data cases By jinlifu1999.