Byte Mountain 是 Byteland 的一个著名旅游景点。Byte Mountain 上有 $n$ 个区域，编号为 $1, 2, \dots, n$，由 $n-1$ 条无向道路连接。每两个不同区域之间恰好有一条路径。换句话说，山上的地图是一棵有 $n$ 个节点的树。

假设今天是第 0 天。在接下来的 $m$ 天里，山上的地图会发生一些变化。具体来说，在第 $i$ 天（$1 \le i \le m$）的清晨，第 $k_i$ 条道路将被永久关闭，并会修建一条新的道路，但山上的地图始终保持为一棵树。

你将获得接下来 $m$ 天的道路施工计划，以及 $p$ 名游客的预订信息。第 $i$ 名游客将在第 $a_i$ 天的下午访问第 $b_i$ 个区域，并于当晚离开。

你现在对一些有趣的指标感到好奇。注意，每条道路都有权重。设 $f(u, v)$ 为连接 $u$ 和 $v$ 的唯一路径上所有道路权重的最大值（$u \neq v$）。你将收到 $q$ 次查询。在第 $i$ 次查询中，你将获得两个整数 $c_i$ 和 $d_i$。你需要计算第 $c_i$ 天第 $d_i$ 个区域的以下指标：

$$\sum_{1 \le j \le p, a_j=c_i, b_j \neq d_i} f(b_j, d_i)$$

输入格式

第一行包含四个整数 $n, m, p$ 和 $q$（$2 \le n \le 10^5, 1 \le m, p, q \le 2 \times 10^5$），分别表示区域数量、天数、游客数量和查询数量。

接下来的 $n-1$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$（$1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9$），表示第 $u_i$ 个区域和第 $v_i$ 个区域之间有一条权重为 $w_i$ 的双向道路。第 $i$ 条道路编号为 $i$（$1 \le i < n$）。这 $n-1$ 条道路描述了第 0 天山上的地图。

接下来的 $m$ 行，每行包含四个整数 $k_i, u_i, v_i$ 和 $w_i$（$1 \le k_i \le n-2+i, 1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9$），表示在第 $i$ 天，第 $k_i$ 条道路将被永久关闭，并在第 $u_i$ 个区域和第 $v_i$ 个区域之间修建一条编号为 $n-1+i$ 的新道路，其权重为 $w_i$。保证山上的地图始终是一棵树，且没有道路会被关闭超过一次。

接下来的 $p$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i \le m, 1 \le b_i \le n$），描述一名游客的预订。

接下来的 $q$ 行，每行包含两个整数 $c_i$ 和 $d_i$（$1 \le c_i \le m, 1 \le d_i \le n$），描述一个查询。

输出格式

对于每个查询，输出一行，包含一个整数，表示答案。

样例

输入 1

5 3 6 6
1 2 9
1 3 4
1 4 6
4 5 2
3 3 5 3
2 1 5 5
5 3 4 8
1 3
2 1
3 3
2 4
1 5
2 4
1 1
1 3
2 5
2 3
3 1
3 3

输出 1

8
3
9
11
8
0