在狐狸座（Vulpecula）星座的中心，栖息着一只小狐狸。它位于一个拥有众多明亮恒星的区域，但其自身相对暗淡。即使是该星座中最亮的恒星，其视星等也仅为 4.44。然而，尽管它很暗淡，狐狸座还是因各种原因吸引了许多观星者的注意。比如，我们问题的男主角 Mu，他将狐狸座视为他最喜欢的星座，因为在那里，他总能看到自己的倒影。

Mu 的生活压力很大，只有通过观星他才能找到一丝慰藉。每天晚上，他都会爬上屋顶，用望远镜观察天空，辨认各种形状的星座。在欣赏宇宙奇观的同时，他偶尔会写下脑海中闪过的想法。而这一晚，是从一个奇怪的问题开始的：“世间的梦想究竟是为了什么？”

Mu 若有所思地抬头看着那只星空中的狐狸，往事如潮水般涌上心头。尽管近年来生活更加艰难，但他对梦想的追求从未减弱。他放弃了金钱，因为他不应过分看重它。他放弃了名望，因为他无法维持它。他放弃了渴望定居的地方，因为他不配拥有它。他放弃了一切，除了……

“梦想就像星星，遥远且有时微不足道，但足以点亮最黑暗的夜晚。”

Mu 在纸条上写下这句话，挤出一丝微笑，随后再次沉浸在观星的乐趣中。

现在，让我们回到问题本身。自古以来，人们就将星座与动物和神话人物联系在一起。他们发挥想象力，在星图上将恒星之间连成直线，并构思出每个星座背后的故事。假设狐狸座中有 $n$ 颗恒星，编号从 $1$ 到 $n$，并有 $n-1$ 条虚构的连线将它们连接起来。也就是说，对于每一对恒星 $(s, t)$，总是存在一个恒星序列 $u_0, u_1, \dots, u_k$，其中 $u_0 = s$ 且 $u_k = t$，满足对于每个 $i = 1, 2, \dots, k$，恒星 $u_{i-1}$ 和恒星 $u_i$ 之间都有一条连线。恒星 $s$ 和恒星 $t$ 之间的距离定义为所有此类序列中 $k$ 的最小值。

Mu 准备观察狐狸座中的这些恒星，他会将望远镜聚焦在 $n$ 颗恒星中的某一颗上。然而，详细的观测需要先进的技术，因为会有几个障碍。

其中之一是有些恒星可能太小而无法观测。为了解决这个问题，Mu 可以转动旋钮进行放大或缩小。具体来说，在选择聚焦的恒星后，他会将焦距调整为一个 $0$ 到 $n-1$ 之间的整数 $d$，并观察所有与聚焦恒星距离不超过 $d$ 的恒星。

另一个障碍是有些恒星可能太暗而无法观测。幸运的是，Mu 可以使用滤镜来调节恒星的光线。令 $a_i$ 表示恒星 $i$ 的可见度，初始值为 $0$。一个标记为 $(i, x)$ 的滤镜仅适用于恒星 $i$，当 Mu 安装它时，$a_i$ 将变为 $a_i \oplus x$，其中 $\oplus$ 表示按位异或运算。Mu 可以挑选他拥有的滤镜集合，并以任意顺序安装它们。他也可以选择不使用滤镜，或者使用两个或多个相同的滤镜。

为了获得愉快的观星体验，Mu 会使视野内恒星的可见度相等并最大化。操作望远镜很容易，但你的任务并不简单。假设 $f(d)$ 是在特定焦距 $d$ 下的最大可见度。对于每一颗恒星，如果它是聚焦恒星，你能计算出 $f(d)$ 在 $d = 0, 1, \dots, n-1$ 上的和对 $2^{64}$ 取模的结果吗？

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 5 \times 10^4$)，表示狐狸座中恒星的数量。

第二行包含 $n-1$ 个整数 $p_1, p_2, \dots, p_{n-1}$ ($1 \le p_i \le i$)，表示对于每个 $i = 1, 2, \dots, n-1$，恒星 $p_i$ 和恒星 $i+1$ 之间存在一条虚构的连线。保证给定的 $n-1$ 条虚构连线连接了所有恒星。

在接下来的 $n$ 行中，第 $i$ 行首先包含一个整数 $m_i$ ($m_i \ge 0$)，表示应用于恒星 $i$ 的滤镜数量。随后是 $m_i$ 个整数 $x_{i,1}, x_{i,2}, \dots, x_{i,m_i}$ ($0 \le x_{i,j} < 2^{64}$)，其中第 $j$ 个表示一个滤镜 $(i, x_{i,j})$。保证所有 $i = 1, 2, \dots, n$ 的 $m_i$ 之和不超过 $2 \times 10^6$。

输出格式

输出 $n$ 行，第 $i$ 行包含一个整数，表示如果恒星 $i$ 是聚焦恒星，则 $f(d)$ 在 $d = 0, 1, \dots, n-1$ 上的和对 $2^{64}$ 取模的结果。

样例

输入 1

2
1
2 2 3
2 1 1

输出 1

4
2

输入 2

5
1 2 2 3
3 83 75 58
4 125 124 58 16
4 39 125 71 112
3 69 66 5
4 48 73 69 6

输出 2

171
125
183
142
243

说明

在第一个样例中，如果恒星 $1$ 是聚焦恒星，Mu 可以安装滤镜 $(1, 3)$ 以达到 $f(0) = 3$，因为当 $d = 0$ 时，恒星 $1$ 是视野中唯一的恒星。他可以依次安装滤镜 $(1, 2)$、滤镜 $(1, 3)$ 以及滤镜 $(2, 1)$ 中的任意一个来达到 $f(1) = 1$。因此，恒星 $1$ 的和为 $(3 + 1) \pmod{2^{64}} = 4$。

Figure 1. 狐狸座（Vulpecula）星座的星图示意