CF1495E Qingshan and Daniel

青山和 Daniel 要玩一款纸牌游戏。但如果只有两个人玩会很无聊，所以他们总共制造了 $n$ 个机器人来自动进行这场游戏。青山制造的机器人属于第 $1$ 队，Daniel 制造的机器人属于第 $2$ 队。第 $i$ 个机器人属于第 $t_i$ 队。在游戏开始前，第 $i$ 个机器人会获得 $a_i$ 张牌。 这款纸牌游戏的规则如下： - 在开始前，机器人按照编号顺序围成一个圆圈。机器人将按某种顺序依次出牌，每一步只有一个机器人出一张牌。游戏开始时，第 $1$ 个机器人会先出一张牌。之后，机器人按照如下规则行动： - 如果上一次出牌的是第 $i$ 个机器人，则下一个出牌的机器人是距离 $i$ 最近且队伍与 $i$ 不同的机器人。换句话说，只有当 $t_i\ne t_j$ 并且 $dist(i,j)$（定义见下文）最小时，$j$ 才会在 $i$ 之后出牌。 - 如果某个机器人没有牌了，则应立即退出游戏。该机器人在后续步骤中不再被考虑。 - 当没有机器人可以继续出牌时，游戏结束。 我们定义从机器人 $x$ 到机器人 $y$ 的距离为 $dist(x,y)=(y-x+n)\bmod n$。这类似于圆圈上的有向距离。 例如，当 $n=5$ 时，从 $1$ 到 $3$ 的距离为 $dist(1,3)=(3-1+5)\bmod 5=2$，从 $3$ 到 $1$ 的距离为 $dist(3,1)=(1-3+5)\bmod 5=3$。 后来，青山发现观看机器人玩游戏会花费太多时间。她想尽快知道结果。作为青山的粉丝，你需要计算一个数组 $[ans_1,ans_2,\ldots,ans_n]$，其中 $ans_i$ 表示第 $i$ 个机器人在游戏过程中出牌的次数。你需要尽快给出答案！ 为了避免输入数据过大，机器人的队伍和牌数需要通过一些辅助数组在你的代码中生成。

第一行包含一个整数 $n$（$1\le n\le 5\cdot 10^6$），表示参与游戏的机器人数量。 第二行包含一个整数 $m$（$1\le m\le \min(n,200\,000)$）。 接下来的 $m$ 行，每行包含四个整数 $p_i$、$k_i$、$b_i$、$w_i$（$1\le p_i\le n$，$1\le k_i\le 10^9+7$，$0\le b_i,w_i

请输出一个整数 $\left( \prod_{i=1}^{n} ((ans_i \oplus i^2)+1)\right) \bmod 10^9+7$，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

在第一个测试样例中，$a=[5,5,1]$，$t=[1,2,2]$。 第 $1$ 个机器人先出牌。 然后第 $2$ 个机器人出牌。第 $3$ 个机器人不会出牌，因为 $dist(1,2)