题目描述

给定一棵有 $N$ 个节点的带权树，初始所有节点均为白色。接下来需要依次处理 $Q$ 个操作：

• 类型 $1$：给定节点 $x$，将节点 $x$ 染成蓝色。若它已经是蓝色，则状态不变。
• 类型 $2$：给定节点 $x$，求 $x$ 到所有蓝色节点的距离之和。

树和全部操作并不会直接输入，而是由以下随机数发生器生成。初始 curValue = startSeed：

nextRandom():
    curValue = (curValue * 1999 + 17) mod 1000003
    return curValue

建树过程如下。对 $i=0,1,\ldots,N-2$：

distance[i] = nextRandom() mod maxDist
parent[i] = nextRandom()
if parent[i] < threshold:
    parent[i] = i
else:
    parent[i] = parent[i] mod (i+1)

随后加入一条连接节点 $i+1$ 与 $parent_i$、长度为 $distance_i$ 的边。

操作生成方式如下。对 $i=0,1,\ldots,Q-1$：

queryType[i] = nextRandom() mod 2 + 1
queryNode[i] = nextRandom() mod N

请按顺序执行全部操作，并把所有类型 $2$ 操作的答案进行按位异或，输出最终结果。

输入格式

一行输入五个整数：

N Q startSeed threshold maxDist

输出格式

输出一个整数，表示所有类型 $2$ 查询答案的按位异或值。

数据范围

$2\le N\le100000$，$1\le Q\le100000$。

$0\le startSeed\le1000002$，$0\le threshold\le1000003$，$1\le maxDist\le1000003$。

样例

输入

4 6 15 2 5

输出

7