问题描述

小 L 出了一个和 DAG 有关的问题并打算投给联合省选。虽然题目很烂，但因为是题，所以被纳入了被选题当中。小 L 因此很不重视，决定脚造数据。

然而，联合省选前一天，DAY1 T2 被爆破了，于是小 L 的题就变成了 DAY1 T2，并且因为小 L 太懒，所以没有重造数据。不出意外的话，意外发生了，小 L 的题被大量暴力通过了。

以上内容纯属虚构。

小 L 追忆了一下造数据的过程，发现他生成的 DAG 其实是按照以下方式生成的：

对于 $i=2\sim n$，$a_i,b_i$ 在 $1\sim i-1$ 中随机生成，然后 $i$ 向 $a_i,b_i$ 连有向边。

小 L 心想，数据既然是随机的，那么这个 DAG 处理起来肯定就很简单，于是给了你 $n-1$ 个询问，第 $i\;(1\le i<n)$ 个询问有参数 $x_i\;(1\le x_i\le i)$，求 $i+1$ 到 $x_i$ 的最短路，如果 $i+1$ 无法到达 $x_i$ 则输出 $-1$。

输入格式

第一行两个正整数 $n,seed$，其中 $seed$ 是用来生成 $a_i,b_i$ 的随机种子。

具体的，$a_i,b_i$ 按照如下程序生成：

unsigned shift(unsigned &a)
{
	a^=a<<13;
	a^=a>>7;
	a^=a<<17;
	return a;
}
void init(unsigned seed)
{
	for(int i=2;i<=n;i++)
		a[i]=shift(seed)%(i-1)+1,
		b[i]=shift(seed)%(i-1)+1;
}

保证 $seed$ 在 $[1,2^{32})$ 中随机生成。

第二行 $n-1$ 个正整数 $x_1,x_2,\cdots,x_{n-1}$。

输出格式

记第 $i$ 次询问的答案为 $s_i$，由于输出量过大，你只需要输出 $\oplus_{i=1}^{n-1}(s_i+2)\times i$ 即可，其中 $\oplus$ 为异或运算。

输入样例

10 1
1 1 2 1 2 3 1 2 3

输出样例

17

样例1解释

$a_{2\sim 10}$ 分别为 $1,2,2,4,1,5,1,4,9$。

$b_{2\sim 10}$ 分别为 $1,2,3,2,1,1,6,7,9$。

$s_{1\sim 9}$ 分别为 $1,2,1,2,-1,3,1,2,3$。

数据范围

特殊性质 A：保证 $x_i$ 在 $1\sim i$ 中随机生成。

特殊性质 B：保证 $x_i\le 10^3$。