CF1495E.Qingshan and Daniel

Qingshan and Daniel are going to play a card game. But it will be so boring if only two persons play this. So they will make $n$ robots in total to play this game automatically. Robots made by Qingshan belong to the team $1$, and robots made by Daniel belong to the team $2$. Robot $i$ belongs to team $t_i$. Before the game starts, $a_i$ cards are given for robot $i$.

The rules for this card game are simple:

• Before the start, the robots are arranged in a circle in the order or their indices. The robots will discard cards in some order, in each step one robot discards a single card. When the game starts, robot $1$ will discard one of its cards. After that, robots will follow the following rules:
• If robot $i$ discards the card last, the nearest robot whose team is opposite from $i$'s will discard the card next. In another word $j$ will discard a card right after $i$, if and only if among all $j$ that satisfy $t_i\ne t_j$, $dist(i,j)$ (definition is below) is minimum.
• The robot who has no cards should quit the game immediately. This robot won't be considered in the next steps.
• When no robot can discard the card next, the game ends.

We define the distance from robot $x$ to robot $y$ as $dist(x,y)=(y-x+n)\bmod n$. It is similar to the oriented distance on the circle.

For example, when $n=5$, the distance from $1$ to $3$ is $dist(1,3)=(3-1+5)\bmod 5=2$, the distance from $3$ to $1$ is $dist(3,1)=(1-3+5)\bmod 5 =3$.

Later, Qingshan finds out that it will take so much time to see how robots play. She wants to know the result as quickly as possible. You, as Qingshan's fan, are asked to calculate an array $[ans_1,ans_2,\ldots,ans_n]$ — $ans_i$ is equal to the number of cards, that $i$-th robot will discard during the game. You need to hurry!

To avoid the large size of the input, the team and the number of cards of each robot will be generated in your code with some auxiliary arrays.

青山和丹尼尔将玩一个纸牌游戏。但如果只有两个人玩，这个游戏会非常无聊。因此，他们将总共制造 $n$ 个机器人来自动进行此游戏。青山制造的机器人属于队伍 $1$，丹尼尔制造的机器人属于队伍 $2$。机器人 $i$ 属于队伍 $t_i$。游戏开始前，机器人 $i$ 被分发 $a_i$ 张牌。

该纸牌游戏的规则如下：

• 游戏开始前，机器人按其编号顺序围成一个圆圈。机器人将按某种顺序弃牌，每一步恰好有一个机器人弃掉一张牌。游戏开始时，机器人 $1$ 首先弃掉其手中的一张牌。此后，机器人遵循以下规则：
• 若机器人 $i$ 刚刚弃掉一张牌，则下一个弃牌的机器人 $j$ 是所有满足 $t_i \ne t_j$ 的机器人中，到 $i$ 的距离 $dist(i,j)$（定义见下文）最小的那个（即与 $i$ 所属队伍相反的最近机器人）。换言之，$j$ 紧接在 $i$ 之后弃牌，当且仅当在所有满足 $t_i \ne t_j$ 的 $j$ 中，$dist(i,j)$ 取得最小值。
• 当某机器人手中已无牌时，它必须立即退出游戏；此后该机器人在后续步骤中不再被考虑。
• 当不存在任何机器人可以继续弃牌时，游戏结束。

我们定义机器人 $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$ 个机器人在整个游戏中弃掉的牌数。请务必加快速度！

为避免输入规模过大，每个机器人的所属队伍及初始手牌数将在你的代码中通过某些辅助数组生成。

The first line contains one integer $n$ ($1 \le n \le 5\cdot 10^6$) — the number of robots playing this game.

The second line contains one integer $m$ ($1 \le m \le \min(n,200\,000)$).

Each of the next $m$ line contains four integers $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 \lt k_i$). It's guaranteed that $p_m=n$ and $p_{j-1} \lt p_{j}$ ($2 \le j \le m$).

Arrays $a_j$ and $t_j$ should be generated by the following pseudo code:

seed = 0
base = 0

function rnd():
ret = seed
seed = (seed * base + 233) mod 1000000007
return ret

p[0] = 0
for i = 1 to m:
seed = b[i]
base = w[i]
for j = p[i - 1] + 1 to p[i]:
t[j] = (rnd() mod 2) + 1
a[j] = (rnd() mod k[i]) + 1

第一行包含一个整数 $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 \lt k_i$）。保证 $p_m=n$，且对所有 $2 \le j \le m$ 有 $p_{j-1} \lt p_{j}$。

数组 $a_j$ 和 $t_j$ 应通过以下伪代码生成：

seed = 0
base = 0

function rnd():
ret = seed
seed = (seed * base + 233) mod 1000000007
return ret

p[0] = 0
for i = 1 to m:
seed = b[i]
base = w[i]
for j = p[i - 1] + 1 to p[i]:
t[j] = (rnd() mod 2) + 1
a[j] = (rnd() mod k[i]) + 1

Print a single integer $\left( \prod_{i=1}^{n} ((ans_i \oplus i^2)+1)\right) \bmod 10^9+7$, where $\oplus$ denotes the bitwise XOR operation.

输出一个整数 $\left( \prod_{i=1}^{n} ((ans_i \oplus i^2)+1)\right) \bmod 10^9+7$，其中 $\oplus$ 表示按位异或运算。

In the first test case $a=[5,5,1]$ and $t=[1,2,2]$.

The robot $1$ discards the card first.

Then robot $2$ discards the card next. Robot $3$ doesn't discard the card next because $dist(1,2) \lt dist(1,3)$.

Then robot $1$ discards the card next. Robot $3$ doesn't discard the card next because $t_2=t_3$.

If we write down the index of the robot who discards a card in time order, it will be the sequence $[1,2,1,2,1,2,1,2]$. So robots $1$, $2$ and $3$ discard $5$, $5$ and $0$ cards, respectively. And the answer is $(((5 \oplus 1^2)+1)\times((5 \oplus 2^2)+1)\times((0 \oplus 3^2)+1)) \bmod 10^9+7=(5\times 2 \times 10)\bmod 10^9+7=100$.

在第一个测试用例中，$a=[5,5,1]$ 且 $t=[1,2,2]$。

机器人 $1$ 首先丢弃卡片。

接着机器人 $2$ 丢弃卡片。机器人 $3$ 此时不会丢弃卡片，因为 $dist(1,2) \lt dist(1,3)$。

然后机器人 $1$ 再次丢弃卡片。机器人 $3$ 此时仍不会丢弃卡片，因为 $t_2=t_3$。

若按时间顺序写出每次丢弃卡片的机器人编号，则得到序列 $[1,2,1,2,1,2,1,2]$。因此，机器人 $1$、$2$ 和 $3$ 分别丢弃了 $5$、$5$ 和 $0$ 张卡片。答案为 $(((5 \oplus 1^2)+1)\times((5 \oplus 2^2)+1)\times((0 \oplus 3^2)+1)) \bmod 10^9+7=(5\times 2 \times 10)\bmod 10^9+7=100$。