首先，给定一个正整数 $MOD$。 你有一个背包，初始时是空的。 你需要执行 $Q$ 次查询。
- 在每次查询中，你必须先执行 ADD 或 REMOVE 操作，然后执行 FIND 操作。
- 对于 ADD 操作，给定正整数 $w$ 和 $v$。你将一个重量为 $w$、价值为 $v$ 的饼干放入背包中。
- 对于 REMOVE 操作，你从背包中取出重量最小的饼干并吃掉它。
- 在每次 ADD 或 REMOVE 操作之后，你执行 FIND 操作：给定正整数 $l$ 和 $r$，回答以下问题：能否从背包中选择一些饼干，使得 $l \le (X \pmod{MOD}) \le r$（其中 $X$ 是所选饼干的重量之和）？如果不能，输出 $-1$。否则，输出所选饼干价值之和的最大值。
输入格式
输入按以下格式给出：
$MOD$ $Q$ $t'_1 \ w'_1 \ v'_1 \ l'_1 \ r'_1$ $t'_2 \ w'_2 \ v'_2 \ l'_2 \ r'_2$ $\dots$ $t'_Q \ w'_Q \ v'_Q \ l'_Q \ r'_Q$
数据范围
$0 \le t'_i, w'_i, v'_i, l'_i, r'_i \le 2^{30} - 1$，$2 \le MOD \le 500$，$1 \le Q \le 100\,000$。
查询已加密，具体描述如下。你可以通过解密 $t'_i, w'_i, v'_i, l'_i, r'_i$ 得到 $t_i, w_i, v_i, l_i, r_i$。
你可以假设 $1 \le w_i, v_i \le 10^9$，$0 \le l_i \le r_i \le MOD - 1$。当 $t_i = 1$ 时为 ADD+FIND 查询，$t_i = 2$ 时为 REMOVE+FIND 查询（此时 $w_i = v_i = 0$）。此外，由 ADD 操作给出的饼干总是比之前所有通过 ADD 添加的饼干更重，且执行 REMOVE 时背包不为空。
我们提供了 C++11（或更高版本）、Java、D 和 C# 的解密代码。请使用 Crypto 类进行解密。Crypto 类的代码及使用示例可从 http://opentrains.mipt.ru/~ejudge/crypto.zip 下载。
输出格式
对于每次查询，打印 FIND 操作的结果。
样例
样例输入 1
10 7 281614559 249378726 433981056 466775634 683612866 727071329 787572584 591471796 328464426 757737734 279580343 240336097 538846427 808491898 224313807 222498984 42804452 371605808 667115067 791865961 68683864 1045549765 515479514 1067782238 349547144 907343711 381772625 149003422 879314974 953881571 883899098 700164610 414212891 752949213 972845634
样例输出 1
10 0 -1 21 -1 11 111
样例输入 2
7 20 281614559 249378726 433981094 466775639 683612870 59536386 999828879 241246766 434670565 174365647 172060134 848462699 857413429 182122460 807914643 808426426 600772095 829463884 974102196 354283529 370037909 1024921880 664216868 194331103 140834169 917331875 242953442 205247688 335469789 1055568137 823475244 641321246 617915164 160300810 1073617378 892669150 939175632 904628449 606339993 1059849410 829170894 436718235 288920513 228195002 55212938 772189413 373108543 94133155 610930061 513937768 986619331 175674265 812546186 865335970 605634588 880196843 1071068047 723408215 587598264 380801783 393196081 141080294 584230885 135343295 661927186 5740819 967233824 22597607 888639499 467454437 365679801 515258603 989059385 962028117 761163096 357270919 737051059 569528959 935653628 70506031 869282414 947492121 280522456 96822010 856514221 155948699 826430734 291243254 381421299 617876780 980891674 833928389 1048677341 522527723 223764850 50617939 963598173 281959650 499436870 47455938
样例输出 2
0 134 90 158 -1 22 238 269 179 189 121 53 41 41 -1 58 -1 84 -1 149