题目描述

给定一个有向图，图中有 $n$ 个顶点, $p$ 条边，编号从 $1$ 到 $n$。初始时，每个顶点的点权值均为 $0$。接下来，会进行 $m$ 次操作，每次操作指定一个顶点 $u$ 和一个正整数 $x$，表示将顶点 $u$ 指向的所有顶点（除了自己）的点权值都增加 $x$。每一轮操作每个顶点只增加一次，在所有操作完成后，求出每个顶点的点权值。

输入格式

• 第一行包含三个整数 $n$、$m$ 和 $p$，分别表示顶点数、操作数和有向边数。
• 接下来 $p$ 行，每行包含两个整数 $u$ 和 $v$，表示一条有向边，其中 $u$ 是边的起点，$v$ 是边的终点。
• 接下来 $m$ 行，每行包含两个整数 $u$ 和 $x$，表示一次操作，其中 $u$ 是操作的顶点编号，$x$ 是增加的点权值。

输出格式

输出一行，包含 $n$ 个整数，分别表示每个顶点的点权值，用空格隔开。

样例

样例输入

4 3 5
1 2
1 3
2 4
1 1
1 2
1 2
2 3
3 4

样例输出

0 2 2 3

解释

• 初始时，所有顶点的点权值为 $0$。
• 第一次操作，顶点 $1$ 的出边指向顶点 $2$ 和 $3$，顶点 $2$ 和 $3$ 的点权值分别增加 $2$。
• 第二次操作，顶点 $2$ 的出边指向顶点 $4$，顶点 $4$ 的点权值增加 $3$。
• 第三次操作，顶点 $3$ 的出边指向顶点没有，不需要增加。
• 最终，顶点 $1$ 的点权值为 $0$，顶点 $2$ 的点权值为 $2$，顶点 $3$ 的点权值为 $2$，顶点 $4$ 的点权值为 $3$。

数据范围

• $1 \leq n \leq 10^5$
• $1 \leq m \leq 10^5$
• $1 \leq p \leq 10^5$
• $1 \leq u, v \leq n$
• $1 \leq x \leq 10^9$
• 每个顶点的出边数量不超过 $10^5$

非简单图(有重边和自环)