题目描述

有 $N$ 个城镇，编号为 $0,1,\ldots,N-1$，由 $N-1$ 条双向公路连接成一棵树，并以 $0$ 号城镇为根。公路具有非负长度。

对于每个顶点 $v$，记 $T(v)$ 为以 $v$ 为根的子树。

商人准备在 $T(v)$ 中选择一个城镇 $b$ 作为基地，并依次前往子树中的所有城镇。与基地选择有关的代价为

$\sum_{w\in T(v)}\operatorname{dist}(b,w)$。

令 $D(v)$ 为上述代价的最小值，其中基地 $b$ 必须属于 $T(v)$。

树并不直接给出，而是由参数 $N,seed,C,D$ 生成。令 cur = seed，对于 $i=0,1,\ldots,N-2$ 执行：

cur = (C * cur + D) mod 10^9
par[i] = cur mod (i + 1)
cur = (C * cur + D) mod 10^9
L[i] = cur mod 10^6

随后加入一条连接 par[i] 与 $i+1$ 的边，其长度为 L[i]。

请计算所有 $D(v)$，并输出它们的按位异或值：

$D(0)\oplus D(1)\oplus\cdots\oplus D(N-1)$。

输入格式

一行输入四个整数 $N,seed,C,D$。

输出格式

输出一个整数，表示所有 $D(v)$ 的按位异或值。

数据范围

• $1\le N\le 300000$；
• $0\le seed,C,D\le 10^9$。

样例

输入

6 8 3 13

输出

856320