一年中竞争最激烈、赌注最高的赛车比赛之一——国际残酷与专业赛车比赛（International Cutthroat and Professional Car-racing competition，又称 ICPC）的时间到了。

今年的赛道是一个由 $n$ 个检查点组成的连通网络，编号为 $1$ 到 $n$。这些检查点由 $n - 1$ 条等长（单位长度）的隧道连接，使得任意两个检查点之间都相互可达。在比赛开始前，赛车手们会在赛道的各个检查点生成，他们的目标是通过最短路径冲向终点检查点。

赛道上的某些检查点是特殊检查点，它们只允许最多 $k$ 名赛车手通过。换句话说，只有最快到达的 $k$ 名赛车手能够通过每个这样的检查点，而其余试图通过的赛车手将被淘汰出局。如果多名赛车手在完全相同的时间到达某个特殊检查点，则速度较快（即通过单位长度隧道所需时间较短）的赛车手优先通过。在特殊检查点生成的赛车手被视为立即通过了该检查点，这也会计入该检查点的 $k$ 名通过名额中。

作为 ICPC 的狂热粉丝，你已知今年赛事中每位赛车手车辆的速度，且每位赛车手的车速在整个比赛过程中保持不变。你想通过计算每位赛车手到达终点检查点所需的时间来预测排行榜。

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$（$2 \le n \le 2 \cdot 10^5$，$1 \le m \le n - 1$，$1 \le k \le 10$），其中 $n$ 是赛道中的检查点数量，$m$ 是赛车手数量，$k$ 是每个特殊检查点允许通过的最大赛车手数量。

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

接下来的 $m$ 行，每行描述一名赛车手。第 $i$ 行包含两个整数 $p$ 和 $t$（$1 \le p \le n$，$1 \le t \le 10^9$），表示第 $i$ 名赛车手在检查点 $p$ 生成，其车辆通过单位长度的隧道需要 $t$ 秒。没有两名赛车手在同一个检查点生成。没有两名赛车手拥有相同的车速，即所有的 $t$ 值互不相同。

下一行包含一个整数 $e$（$1 \le e \le n$），表示终点检查点。没有赛车手在终点检查点生成。

下一行包含一个整数 $c$（$1 \le c \le n - 1$），表示特殊检查点的数量。

接下来的 $c$ 行，每行包含一个整数 $x$（$1 \le x \le n$，$x \ne e$），表示检查点 $x$ 是一个特殊检查点。所有 $c$ 个特殊检查点互不相同。

输出格式

输出 $m$ 行。在第 $i$ 行，输出第 $i$ 名赛车手到达终点检查点所需的秒数。如果第 $i$ 名赛车手被特殊检查点阻挡并被淘汰，则输出 $-1$。

图 L.1：样例情况示意图。检查点 2 是终点检查点。检查点 1 和 6 是特殊检查点（以灰色显示）。

样例

输入样例 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

输出样例 1

6
-1
-1
4
-1