# #656. 【ULR #2】霸占排行榜

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

$u_i$ （$1 < i \le 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



### 限制与约定

$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$