#1996. The kth maximum number

The kth maximum number

Description

神犇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的每次询问。

Format

Input

输入的第一行为两个正整数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

Output

对于每个询问(type=2的操作),回答第k大的贡献。若不存在第k大的贡献,请输出"NAIVE!ORZzyz."(输出不含双引号)。

Samples

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