Qingshan and Daniel

题意翻译

$n$ 个机器人站在一个环上打三国杀，第 $i\ (1 \le i < n)$ 个机器人的相邻右侧站着 $i+1$ 号机器人。特别地，$n$ 号机器人的相邻右侧是 $1$ 号机器人。 机器人分两个阵营，第 $i$ 个机器人属于阵营 $t_i$，初始有 $a_i$ 张【无懈可击】。 游戏会以如下方式进行： - 初始 $1$ 号机器人打出一张手牌。 - 假设最近一次出【无懈可击】的机器人是 $i$，找到它右侧离它最近与它不同阵营的拥有牌的机器人 $j$，$j$ 出一张【无懈可击】。 - 当无人能出牌时游戏停止。 求每一个机器人最终出了多少张无懈可击。 Imakf 给您的输入输出格式均进行了压缩，请自行查看。

题目描述

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.

输入输出格式

输入格式

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< k_i $ ). It's guaranteed that $ p_m=n $ and $ p_{j-1}<p_{j} $ ( $ 2 \le j \le n $ ). 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 ```

输出格式

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](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

输入输出样例

输入样例 #1

3
3
1 5 2 3
2 7 1 2
3 2 1 1

输出样例 #1

100

输入样例 #2

5000000
2
1919810 998244353 114514 19260817
5000000 233333333 623532 7175

输出样例 #2

800210675

输入样例 #3

1
1
1 1 0 0

输出样例 #3

1

说明

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)<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 $ .

题意翻译

$n$ 个机器人站在一个环上打三国杀，第 $i\ (1 \le i < n)$ 个机器人的相邻右侧站着 $i+1$ 号机器人。特别地，$n$ 号机器人的相邻右侧是 $1$ 号机器人。 机器人分两个阵营，第 $i$ 个机器人属于阵营 $t_i$，初始有 $a_i$ 张【无懈可击】。 游戏会以如下方式进行： - 初始 $1$ 号机器人打出一张手牌。 - 假设最近一次出【无懈可击】的机器人是 $i$，找到它右侧离它最近与它不同阵营的拥有牌的机器人 $j$，$j$ 出一张【无懈可击】。 - 当无人能出牌时游戏停止。 求每一个机器人最终出了多少张无懈可击。 Imakf 给您的输入输出格式均进行了压缩，请自行查看。