题目描述

有一条赛车赛道，由 $n$ 个检查点组成，检查点之间通过 $n-1$ 条长度为 1 的隧道连接，整体构成一棵树。

比赛开始前，有 $m$ 名赛车手分别出生在不同的检查点，他们的目标是沿最短路到达终点检查点。每名赛车手通过一条单位长度隧道所需时间不同，且速度保持不变。

某些检查点是特殊检查点，每个特殊检查点只允许最快到达的 $k$ 名赛车手通过。若多名赛车手同时到达，则速度更快者优先通过。若赛车手出生在特殊检查点，则视为已经立即通过该检查点，并计入这 $k$ 名之中。

请预测每名赛车手到达终点所需时间；若会被某个特殊检查点淘汰，则输出 -1。

输入格式

第一行包含三个整数 $n,m,k$：

$$2\le n\le 2\cdot 10^5, \qquad 1\le m\le n-1, \qquad 1\le k\le 10.$$

接下来 $n-1$ 行，每行包含两个整数 $a,b$，表示一条隧道连接检查点 $a,b$。

接下来 $m$ 行，第 $i$ 行包含两个整数 $p,t$，表示第 $i$ 名赛车手出生在检查点 $p$，并且通过一条单位长度隧道需要 $t$ 秒。

保证没有两名赛车手出生在同一检查点，没有赛车手出生在终点，且所有 $t$ 互不相同。

接下来一行包含一个整数 $e$，表示终点检查点。

接下来一行包含一个整数 $c$，表示特殊检查点数量。

接下来 $c$ 行，每行一个整数 $x$，表示检查点 $x$ 是特殊检查点。保证 $x\ne e$，且所有特殊检查点互不相同。

输出格式

输出 $m$ 行，第 $i$ 行表示第 $i$ 名赛车手到达终点所需秒数；若该赛车手会被淘汰，则输出 -1。

样例 #1

输入

8 5 2
2 1
1 3
4 5
1 4
4 6
6 7
6 8
5 2
3 4
6 3
7 1
8 5
2
2
1
6

输出

6
-1
-1
4
-1