题目背景

安慰一个伤心的人，真的好困难呢……

在好友最需要自己的时候，明明有很多话可说，却只会“好惨”“拍拍”“抱抱”什么的，真的很让人自责啊。

如果萝卜能让所有人对感情认真起来，像她这样被伤害的人，是不是就会少一些呢？

题目描述

小 C 被分手了，这让小 C 联想起了许多不高兴的事，她现在很伤心。而小萝卜正在试图让她的心重归平静。

现在有 $n$ 个事件困扰着小 C。根据小 C 的联想过程，这些事件可以看做一棵根为 $1$ 的外向树，其中边 $(u,v)$ 表示 $v$ 是由 $u$ 联想产生的，而点 $1$ 到点 $u$ 的距离称作 $u$ 的联想距离。同时每件事 $u$ 都有一个难过程度 $a_u$。

小萝卜每次可以进行两种操作其一：

• 安慰小 C：选择一个事件并将其子树内所有事件的难过程度 $-1$。
• 抱抱小 C：选择一个数 $x$ 并将所有联想距离为 $x$ 的点的难过程度 $-1$。

对于每个点 $u$，设 $ans_u$ 表示使 $u$ 子树内的所有事件的难过程度都恰好为 $0$ 的最少操作数（$u$ 子树外的事件没有限制），无解则 $ans_u=-1$。小萝卜需要对所有 $i$ 求出 $ans_i$。其中各询问独立。

特别地，为防止输出量过多，只需要输出所有 $ans_i+1$ 的异或和即可。保证做法与此部分无关。

由于小 C 快要破防了，小萝卜只有 0.5 s 的时间。

输入格式

由于输入量过大，本题输入文件经过了压缩。你可以通过以下代码来获取树上每个节点 $u$ 的父亲 $p_u$ 与点权 $a_u$：

const int MAXN = 1e6 + 10;

int n, p[MAXN], a[MAXN]; char buf[1 << 24];

inline 
void read() {
	scanf("%d%s", &n, buf);
	for (int i = 2, j = 0; i <= n; i++) {
		for (; ~buf[i + j - 2] & 1; j++);
		p[i] = j;
	}
	scanf("%s", buf);
	for (int i = 1, j = 0; i <= n; i++) {
		a[i] |= buf[j++] - 33 << 24;
		a[i] |= buf[j++] - 33 << 18;
		a[i] |= buf[j++] - 33 << 12;
		a[i] |= buf[j++] - 33 << 6;
		a[i] |= buf[j++] - 33;
	}
}

输出格式

输出一行，一个整数，表示 $\bigoplus^n_{i=1}(ans_i+1)$ 的值。

5
011011
!!!!$!!!!*!!!!&!!!!+!!!!+

0

10
0110011011001101
!!!!F!!!!\!!!![!!!!]!!!!!!!!!"!!!!)!!!!<!!!!B!!!!2

84

30
01100110110010101101010011001101100010100110011010101011
!"8\W!'`ZP!&FV]!(:^T!,3=<!.`:Y!0QB<!1011!0V\]!2I`3!2EU0!1D!A!2W9R!3&9!!2TU$!3[07!5JB>!5PRL!69JG!<^0"!@15"!E!&=!DX^"!KZ$I!IGQ6!R(*G!S3`E![NHW!U>NB!\AC]

5120225

提示

【样例解释 #1】

样例 $1$ 解密后的输入如下：

5
1 1 2 2
3 9 5 10 10

对于 $u=1$，其中一种最优的操作方案如下：

• 选择事件 $1$ 安慰小 C $3$ 次。之后 $a$ 为 $\{0,6,2,7,7\}$。
• 选择事件 $2$ 安慰小 C $6$ 次。之后 $a$ 为 $\{0,0,2,1,1\}$。
• 选择事件 $3$ 安慰小 C $2$ 次。之后 $a$ 为 $\{0,0,0,1,1\}$。
• 选择联想深度 $2$ 抱抱小 C $1$ 次。之后 $a$ 为 $\{0,0,0,0,0\}$。

需要 $12$ 次操作。可以证明并不存在更优的操作方案。对于事件 $u=1\sim 5$，$ans_u$ 分别为 $12,10,5,10,10$，$ans_u+1$ 的异或和为 $0$，故输出 $0$。

【数据范围】

本题采用捆绑测试。

子任务编号	$n\le$	$a_i\le$	特殊性质	分值
$1$	$5$	$10$	无	$5$
$2$	$100$		^	$12$
$3$	$10^3$	$10^9$	AB	$6$
$4$	^	^	A	$8$
$5$			B	$9$
$6$			无	$12$
$7$	$2\times10^5$		B	$13$
$8$	^		无	$14$
$9$	$10^6$		^	$21$

• 特殊性质 A：对于任意 $2 \le u \le n$，保证 $p_u=u-1$。
• 特殊性质 B：对于任意 $2 \le u \le n$，保证 $a_u\ge a_{p_u}$。

对于所有数据，保证 $1\le n\le 10^6$，$0\le a_i\le 10^9$，$1\le p_i<i$。