8604: BZOJ4604：The kth maximum number

神犇Aleph在陪蒟蒻Bob玩一个游戏。神犇Aleph随手在地面上画了一个巨大无比的二维平面，然后在其上做一些微 小的贡献或教蒟蒻Bob做人。由于神犇Aleph是队爷，所以有时他会施用"队爷光环"这一魔法，在二维平面上的某坐 标整点处添加一个权值为v的贡献；又由于神犇Aleph是神犇，所以有时他会施用"嘲讽"这一技能，询问蒟蒻Bob在 矩形区域(x1, y1), (x2, y2)(x1≤x2且y1≤y2，包括边界)中，神犇Aleph所做的第k大的贡献是多少。由于神犇Al eph是Au爷，所以他不会在同一个坐标整点处做两次或两次以上的贡献。现在神犇Aleph希望蒟蒻Bob回答他的每次 询问。然而蒟蒻Bob傻傻不会做，于是来求助您，宇宙第一神犇，请您来回答神犇Aleph的每次询问。

输入格式

输入的第一行为两个正整数N, Q，表示横纵坐标的范围和神犇Aleph的操作次数（包括贡献次数和询问次数）。 接下来Q行，每行代表神犇Aleph的一个操作，操作格式如下： 首先第一个数字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) 初始时平面上不存在贡献。 本题共有7组测试数据。对于所有的数据，N≤500,000。 Q的范围见下表： 测试点1-2 Q=1,000 测试点3-7 Q=50,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.