题目背景

新年快到了，小僖要做一个长远的旅行，至于从哪里开始，到哪里，他还没有想好。

题目描述

这次旅行是在一个由 $N$ 个城市和 $(N-1)$ 条双向道路组成的一个国家中，其中保证任意两个城市可以互达。

为了美化环境，所有道路都是沿河修建的，这意味着小僖可以自己制造一艘船，然后划船通过这条路，所以小僖每走一条边都可以从陆上走过去，也可以划船通过。

当然，因为顺流和逆流的原因，所以有一个参数 $z_i$，换句话讲，如果从陆上走过这条边所花费的时间为 $a_i$，那么顺流而下划船所花费的时间为 $a_i-z_i$ (保证结果大于 $0$)，逆流而上花费的时间为 $a_i+z_i$。不过，造船需要 $L$ 的时间，且人一旦上了岸，就必须放弃这条船只。

现在小僖想你帮忙算一下从 $u$ 走到 $v$ 的最短时间。

注意：一条船可以连续走多段水路（只要你不下船）

输入格式

第一行三个数，$N,L,T$。

接下来 $(N-1)$ 行，每行五个数，$x_i,y_i,a_i,z_i,type_i$，其中 $type_i=1$ 表示水从 $x_i$ 流向 $y_i$，$type_i=0$ 表示水从 $y_i$ 流向 $x_i$。

接下来 $T$ 行，每行两个数 $u_i,v_i$，表示每个计划的起点和终点。

输出格式

$T$ 行，每行一个数，表示每一个询问的答案。

3 2 2
1 2 2 1 0
1 3 3 2 1
2 3
1 2

4
2

4 1 1
1 2 100 99 1
2 3 100 99 0
3 4 100 99 1
1 4

104

提示

样例1解释

图长这样：

对于第一组询问，也就是从 $2$ 到 $3$，我们可以在 $2$ 号节点造船，花费 $2$ 的时间，然后从节点 $2$ 顺流而下到 $1$，花费 $2-1=1$，在顺流而下到 $3$，花费 $3-2=1$，所以总花费为 $2+1+1=4$。

数据范围

对于 $10\%$ 的数据，$N,T\leq10^3$。

对于另外 $10\%$ 的数据，树的形态随机。

对于另外 $20\%$ 的数据，所有的 $u$ 或所有的 $v$ 都相等。

最后一个测试点给出了一条链。

对于 $100\%$ 的数据，$N,T\leq2\times10^5$，且 $0 <a_i,L\leq10^5$。