P4848 Laoshan Baihua Shecao Water

Ace (shenben, “神犇”) Aleph set a flag before SDOI Round 2: if he got into the provincial team, he would livestream himself drinking Laoshan Baihua Shecao Water. With his strength, Aleph easily made it into the Shandong provincial team, and now it is time for him to keep his promise. Rookie (juruo, “蒟蒻”) Bob specially prepared 999,999,999,999,999,999 bottles of Laoshan Baihua Shecao Water, hoping to force Ace Aleph to drink them. Ace Aleph begged (on his knees) rookie Bob not to do that. Since Ace Aleph is an ace, rookie Bob finally agreed, but Bob decided to play along and make Aleph answer some questions. More specifically, rookie Bob will place some Laoshan Baihua Shecao Water on a spacious square (which can be seen as some integer grid points on a 2D plane), and then ask Ace Aleph: within the rectangular region $x_1\le x\le x_2,y_1\le y\le y_2$, what is the $k$-th largest bottle count. To avoid trouble, rookie Bob will not place Laoshan Baihua Shecao Water at the same position twice or more, but he still wants to make things difficult for Ace Aleph, hoping that Aleph can answer immediately for every query. Ace Aleph does not care to solve such a problem, so he hands it to you.

The first line contains two positive integers $n$ and $q$, indicating the coordinate range on both axes and the number of operations by rookie Bob (including both placements and queries). The next $q$ lines each describe one operation by rookie Bob, in the following format: The first number is $\mathrm{type}$, indicating the operation type. $\mathrm{type}=1$ means a placement, and $\mathrm{type}=2$ means a query. If $\mathrm{type}=1$, it is followed by three positive integers $x, y, v$, meaning that $v$ bottles of Laoshan Baihua Shecao Water are placed at the integer point $(x, y)$. If $\mathrm{type}=2$, it is followed by five positive integers $x_1, y_1, x_2, y_2, k$, meaning a query in the rectangular region $x_1\le x\le x_2,y_1\le y\le y_2$: what is the $k$-th largest bottle count. To reflect the online nature of the program, you must XOR every value you read (except the $\mathrm{type}$ value) with $\mathrm{lastans}$, where $\mathrm{lastans}$ is the answer to the previous query. If the previous query answer is `NAIVE!ORZzyz.` (see the sample output), then set $\mathrm{lastans}$ to $0$. Initially, $\mathrm{lastans}$ is $0$. Initially, there is no Laoshan Baihua Shecao Water on the plane.

For each operation with $\mathrm{type}=2$, output one line: the $k$-th largest bottle count. If the $k$-th largest bottle count does not exist, output `NAIVE!ORZzyz.`.

Constraints: For all testdata, $n\le500000$, $q\le100000$, $1\le x, y\le n$, $1\le v\le 10^9$, $1\le x_1\le x_2\le n$, $1\le y_1\le y_2\le n$, $1\le k\le q$. Translated by ChatGPT 5