【ULR #2】霸占排行榜
超级管理员 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}+\dots+s_{a_m}$。
现在，Skip 蚤想知道，对于每一个账号名 $u_i(1 < i \le l)$，在自己的账号名 $T$ 中出现的次数 $ans_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$。
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
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 fa_i\le l, 1\le w\le 4\times 10^6$，所有输入的字符 $\in [1,w]$。
保证输入的 $fa$ 构成一棵以 $1$ 为根的树。
| 子任务编号 | $l\le$ | $m\le$ | $S\le$ | $w\le$ | trie树形态 | 分值 |
|---|---|---|---|---|---|---|
| $1$ | $2000$ | $2000$ | $2000$ | $4\times 10^6$ | - | $7$ |
| $2$ | $10^5$ | $10^6$ | $3\times 10^6$ | $fa_i=i-1(1 < i\le n)$ | $14$ | |
| $3$ | $2000$ | $26$ | - | $17$ | ||
| $4$ | $10^5$ | $5\times 10^5$ | $29$ | |||
| $5$ | $3\times 10^6$ | $4\times 10^6$ | $33$ |
时间限制：$3\texttt{s}$
空间限制：$1\texttt{GB}$