# 红石钟

- 参考时间限制：3.0 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：512 MB

## 背景故事

村长想制作能够设置长时间闹铃的红石钟。他把两个时钟同时启动，只有它们同时结束各自的一个周期时，闹铃才会响起。现在要测试一系列动态生成的周期组合，请汇总每组组合第一次响铃的时间。

## 形式化问题描述

给定正整数 $n,a$ ，共进行 $2n$ 次询问。周期为 $s,t$ 的两个时钟都在时刻 $0$ 启动，询问答案为它们第一次同时结束周期的正时刻；时刻 $0$ 不计。

令 $U=10000000$ .对 $i=1,\ldots,n$ ，严格按以下顺序执行：

1. 第 $2i-1$ 次询问使用周期 $i,a$ ，记录答案。
2. 更新 $a\gets(a+10007)\bmod U+1$ .
3. 第 $2i$ 次询问使用周期 $i,a$ ，记录答案。
4. 更新 $a\gets(a^2+1)\bmod U+1$ .

分别输出所有奇数次询问答案的按位异或和，以及所有偶数次询问答案的按位异或和。

## 输入格式

输入一行两个整数 $n,a$ ，其中 $a$ 是初始值。

## 输出格式

输出两行：第一行是奇数次询问答案的异或和，第二行是偶数次询问答案的异或和。

## 样例 1

### 输入

```text
5 7
```

### 输出

```text
8312897
24761077
```

### 解释

按给定顺序生成十次询问。每次更新后的 $a$ 会用于下一次询问。

## 样例 2

### 输入

```text
1 1
```

### 输出

```text
1
10009
```

### 解释

第一次询问的周期为 $1,1$ ，答案为 $1$ .随后 $a$ 更新为 $10009$ ，第二次询问答案为 $10009$ .

## 数据范围与保证

- $1\le n\le10000000$ ，$1\le a\le10000000$ .

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 25% | $n\le1000000$ |
| 75% | 无额外条件 |