U261274 永远亭计数

迷途竹林，永远亭。 妹红没有来，蓬莱山辉夜正在和兔子们打游戏。 - 为什么辉夜总是宅在家里呢？ - 可能是因为永远亭太大了吧，出来不方便。。。

永远亭中有 $n$ 个房间，其中 $i$ 号房间里有一只标号为 $i$ 的兔子。 现在永远亭里面会发生 $m$ 次事件，总共分两种： 1. ```1 l r c``` 辉夜把房间 $[l,r]$ 内的所有兔子全部叫去房间 $c$ 打游戏。 2. ```2 a k opt``` 永琳把房间 $a$ 中编号 最大 $/$ 最小 的 $k$ 只兔子叫走（$opt = 0$ 表示最大，$opt = 1$ 表示最小）。 对于事件 $2$，你需要输出被叫走的兔子的编号之和。 出于某些原因，被叫走的兔子不会再回来。 永远亭里的电脑被辉夜拿去打游戏了，而且永远亭实在是太大了，所以需要你去解决这个问题。

第一行两个正整数 $n, m$。 接下来 $m$ 行，每行 $4$ 个整数表示一个事件。 本题强制在线，请自觉使用在线算法。

共 $m$ 行，对于每个事件 $2$，输出一行一个正整数表示答案。

对于 $100\%$ 的数据，有 $n \le 10^{18}$，$m \le 10^5$。 输出答案对 $10^{9961}$ 取模。 ~~（现在感受到永远亭有多大了吧）~~ 请使用合适的方式存储、输出答案。