# Grox的序列四

- 参考时间限制：1.0 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：1024 MB。
- [参考评测环境与测量](../../../docs/评测环境与性能.md)

## 背景故事

> 知识可以透过探索、观察、收集经验资料、推论、假说和假说实验等过程来获得。
>
> ——科学之书3（《Spore》，[英文资料](https://spore.fandom.com/wiki/Books_of_Science)）

解决了第二道序列问题后，Grox 发现了一种神奇的算法，能够生成一种神奇的序列。这次，序列的构造同时用到了按位异或、按位或与按位与。

Grox 想知道这个序列的值，但为了避免输出过多，只请你计算三个汇总值。

## 形式化问题描述

给定非负整数 $n$ 和两组整数 $a_0,\ldots,a_n$ 、$b_0,\ldots,b_n$ .令 $P=1004535809$ .

对 $0\le t\le n$ ，定义

$$C_t=\sum_{\substack{0\le i,j\le n\\i+j\le n\\i\mathbin{\mathrm{XOR}}j=t}}a_i b_j+\sum_{\substack{0\le i,j\le n\\i+j\le n\\i\mathbin{\mathrm{OR}}j=t}}a_i b_j+\sum_{\substack{0\le i,j\le n\\i+j\le n\\i\mathbin{\mathrm{AND}}j=t}}a_i b_j$$

$\mathrm{XOR}$ 、$\mathrm{OR}$ 、$\mathrm{AND}$ 分别表示按位异或、按位或、按位与。三个求和各自计数；同一有序数对可在不同求和中贡献。

对 $r=0,1,2$ ，计算

$$V_r=\left(\sum_{\substack{0\le t\le n\\t\equiv r\pmod3}}C_t\right)\bmod P$$

空和为 $0$ .输出每个结果的最小非负余数。

## 输入格式

第一行一个整数 $n$ .第二行 $n+1$ 个整数 $a_0,\ldots,a_n$ ；第三行 $n+1$ 个整数 $b_0,\ldots,b_n$ .

## 输出格式

输出三行，依次为 $V_0,V_1,V_2$ .

## 样例

### 样例 1

### 输入

```text
2
1 2 3
3 2 1
```

### 输出

```text
31
24
20
```

### 样例 2

### 输入

```text
0
2
3
```

### 输出

```text
18
0
0
```

### 样例 3

### 输入

```text
3
1 0 2 3
0 4 1 0
```

### 输出

```text
29
8
2
```

## 样例解释

样例一中 $C_0=31,C_1=24,C_2=20$ .样例二中，唯一数对在三个求和中各贡献 $6$ ，所以 $V_0=18$ .

## 数据范围与保证

对 **100% 数据**：

$0\le n\le2^{20}-1$ ；$0\le a_i,b_i\le10^9$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |