超级管理员 Skip 蚤想把自己的 Rating 改成 $8000$。同时，他需要换一个特别长的账号名，这样在 Rating List 上它的名字就会特别显眼。

而且，如果在搜索其它跳蚤时顺便搜索到它，便能提高他的知名度。

UOJ 中的账号名在数据库中由给定一棵有 $l$ 个节点的 trie 树（以 $1$ 为根）存储。

对于树上的某个点 $i$，定义 $u_i$ 为从根节点到 $i$ 的路径上的字符从浅到深顺次连接得到的字符串（$u_1=\varnothing$）。

$u_i$ （$1<i\le l$） 同时是跳蚤的账号名。

超级管理员 Skip 蚤想用如下方式生成自己的账号名 $T$。

给出若干字符串 $s_1,s_2,\dots ,s_n$，令 $T=s_{a_1}+s_{a_2}+\cdots +s_{a_m}$。

现在，Skip 蚤想知道，对于每一个账号名 $u_i(1<i\le l)$，在自己的账号名 $T$ 中出现的次数 $an{s}_i$。

输入格式

输入第一行包含四个正整数 $l,n,m,w$。

接下来一行包含一个 $l-1$ 个正整数，分别表示 $c_2,c_3,\dots ,c_l$，即 trie 树上每个点到父亲的边上的字符。

接下来一行包含 $l-1$ 个正整数，分别表示 ${\mathrm{fa}}_2,{\mathrm{fa}}_3,\dots ,{\mathrm{fa}}_l$，即 trie 树上每个点的父亲。

接下来 $n$ 行，每行首先有一个正整数表示 $|s_i|$，然后 $|s_i|$ 个正整数给出 $s_i$。

接下来一行 $m$ 个正整数，分别表示 $a_1,a_2,\dots ,a_m$。

输出格式

输出一行 $l-1$ 个非负整数，分别表示 ${\mathrm{ans}}_2,{\mathrm{ans}}_3,\dots ,{\mathrm{ans}}_l$。

样例一

input

7 3 6 2
1 2 2 1 1 1
1 1 2 2 3 4
3 1 1 1
4 1 2 1 2
3 2 2 1
1 3 2 3 1 1

output

13 6 3 9 3 1

限制与约定

记 $S=\sum _{i=1}^n|s_i|$。

对于所有数据，保证 $1\le l\le {10}^5,1\le n\le 100,1\le m\le {10}^6,1\le S\le 3\cdot {10}^6,1\le f{a}_i\le l,1\le w\le 4\times {10}^6$，所有输入的字符 $\in [1,w]$。

保证输入的 $fa$ 构成一棵以 $1$ 为根的树。

时间限制：$3\mathtt{\text{s}}$

空间限制：$1\mathtt{\text{GB}}$

下载

样例数据下载