本题数据放过了根号分块的做法，然而就本题的出题方式而言这样的做法完全是可以被卡掉的：只需令 $b \approx n - \sqrt n$ 即可。

原因很简单，在设置了参数 $b$ 时，如下生成询问的代码：

  void genqry(int& l, int& r, int n) {
    if ((rnd() & 1) && b) {
      int c = rnd() % (n - b);
      l = rnd() % (n - c) + 1, r = l + c;
    } ...
  }

这里代码的作用是生成长度为 $c$ 的区间作为询问，其中 $c$ 服从 $[0, n - b)$ 上的均匀分布，从而很容易生成区间很长的询问。

然而区间长的询问越多，并不代表就更难；甚至完全相反的，区间长的询问越多，越是偏袒根号分块和猫树从而跑得奇快无比，因为根据上面关于随机区间的解释和很多题解所说的那样，根号分块对区间长度 $> \sqrt n$ 的都可以 $O(1)$ 计算，猫树对区间长度 $> n/2$ 的都可以一起处理掉，这样的询问偏偏是最多的。

以下是参考的 hack 数据：

样例

样例输入

1000000 1000000 76508 999000
0 0 0 0

样例输出

26621274