Image by Rajesh Misra

有一天，年轻的 Anna 想出了一个奇思妙想，利用一棵树来创建一个数字生成器。该生成器由一个模数 $m$ 和一棵包含 $n$ 个节点的树组成，节点编号从 $1$ 到 $n$。每个树节点都被分配了一个 $0$ 到 $9$ 之间的数字。生成器提供了一个方法 $Get(a, b)$，可用于生成一个 $[0, m)$ 范围内的整数。两个参数 $a$ 和 $b$ 指定了树上的两个节点。生成器会沿着树上从 $a$ 到 $b$ 的路径行走，将路径上的所有数字（包括节点 $a$ 和 $b$ 的数字）连接起来，从而得到一个十进制整数 $v$。注意，$v$ 可能非常大，并且可能包含前导零。$Get(a, b)$ 的返回值是 $v \pmod m$。

给定一棵树以及 Anna 的数字生成器所使用的 $m$ 值，计算 $q$ 次查询 $Get(a, b)$ 的返回值。

输入格式

第一行包含三个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)，$m$ ($1 \le m \le 10^9$) 和 $q$ ($1 \le q \le 2 \cdot 10^5$)。

接下来的 $n - 1$ 行描述了树的边。每行包含两个整数 $x, y$ ($1 \le x, y \le n$)，表示连接节点 $x$ 和节点 $y$ 的一条边。保证这些边构成一棵树。

接下来的 $n$ 行，每行包含一个 $0$ 到 $9$ 之间的数字。第 $i$ 行的数字分配给节点 $i$。

接下来的 $q$ 行，每行包含两个整数 $a, b$ ($1 \le a, b \le n$)，指定了一次查询 $Get(a, b)$。

输出格式

对于每次 $Get(a, b)$ 查询，输出其返回值，每行一个。

样例

输入格式 1

5 100 4
1 2
1 3
1 4
5 3
1
2
3
0
4
1 5
5 1
4 2
3 3

输出格式 1

34
31
12
3