题目描述

请实现 Prüfer 序列和无根树的相互转化。

为方便你实现代码，尽管是无根树，我们在读入时仍将 $n$ 设为其根。

对于一棵无根树，设 $f_{1\dots n-1}$ 为其父亲序列（$f_i$ 表示 $i$ 在 $n$ 为根时的父亲），设 $p_{1 \dots n-2}$ 为其 Prüfer 序列。

另外，对于一个长度为 $m$ 的序列 $a_{1 \dots m}$，我们设其权值为 $\operatorname{xor}_{i = 1}^m i \times a_i$。

输入格式

第一行两个整数 $n,m$，表示树的点数和转化类型。

若 $m = 1$，第二行一行 $n-1$ 个整数，表示父亲序列。
若 $m = 2$，第二行一行 $n-2$ 个整数，表示 Prufer 序列。

输出格式

若 $m = 1$，一行一个整数，表示给出的父亲序列对应的 Prüfer 序列的权值。
若 $m = 2$，一行一个整数，表示给出的 Prüfer 序列对应的父亲序列的权值。

6 1
3 6 4 6 1

29

6 2
4 6 5 2

4

提示

【样例 1 解释】

$p = \{6\ 1\ 3\ 4\}$。

【样例 2 解释】

$f = \{4\ 6\ 6\ 5\ 2\}$。

【数据范围】