红石钟¶
- 参考时间限制：3.0 秒（参考环境：评测环境与性能；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：512 MB
背景故事¶
村长想制作能够设置长时间闹铃的红石钟。他把两个时钟同时启动，只有它们同时结束各自的一个周期时，闹铃才会响起。现在要测试一系列动态生成的周期组合，请汇总每组组合第一次响铃的时间。
形式化问题描述¶
给定正整数 \(n,a\) ，共进行 \(2n\) 次询问。周期为 \(s,t\) 的两个时钟都在时刻 \(0\) 启动，询问答案为它们第一次同时结束周期的正时刻；时刻 \(0\) 不计。
令 \(U=10000000\) .对 \(i=1,\ldots,n\) ，严格按以下顺序执行：
- 第 \(2i-1\) 次询问使用周期 \(i,a\) ，记录答案。
- 更新 \(a\gets(a+10007)\bmod U+1\) .
- 第 \(2i\) 次询问使用周期 \(i,a\) ，记录答案。
- 更新 \(a\gets(a^2+1)\bmod U+1\) .
分别输出所有奇数次询问答案的按位异或和，以及所有偶数次询问答案的按位异或和。
输入格式¶
输入一行两个整数 \(n,a\) ，其中 \(a\) 是初始值。
输出格式¶
输出两行：第一行是奇数次询问答案的异或和，第二行是偶数次询问答案的异或和。
样例 1¶
输入¶
5 7
输出¶
8312897
24761077
解释¶
按给定顺序生成十次询问。每次更新后的 \(a\) 会用于下一次询问。
样例 2¶
输入¶
1 1
输出¶
1
10009
解释¶
第一次询问的周期为 \(1,1\) ，答案为 \(1\) .随后 \(a\) 更新为 \(10009\) ，第二次询问答案为 \(10009\) .
数据范围与保证¶
- \(1\le n\le10000000\) ，\(1\le a\le10000000\) .
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 25% | \(n\le1000000\) |
| 75% | 无额外条件 |