结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

某通信网由 $n$ 个节点和 $m$ 条光缆组成，节点按 $1$ 到 $n$ 编号。光缆均为无向连接，允许重边（两个节点之间可能铺设多条光缆），但没有连接同一节点自身的光缆。在不安排任何检修的情况下，网络是连通的：任意两个节点都能经过若干条光缆互相到达。

每条光缆都规定了带宽，即单位时间里它能承载的信号量。运维部门还为其安排了计划检修：光缆 $e$ 的检修窗口为 $[l_e, r_e]$（含两端），窗口时刻为整数，满足 $0 \le l_e \le r_e \le T$。在窗口内的每个时刻，该光缆停用，不参与任何通路；在窗口外的时刻，该光缆正常工作。各条光缆的检修计划互不影响。

信号沿一条通路传播的每个时刻，通路上每条光缆都必须正常；整条通路的速率受限于其中带宽最小的那条光缆。因此一条通路的可用速率定义为通路上各光缆带宽的最小值。

调度台陆续收到 $q$ 次查询，每次查询给出两个节点 $u, v$ 与一个时刻 $t$，需要回答：在时刻 $t$ 正常工作的光缆中，$u$ 与 $v$ 之间的通路可用速率的最大值。若时刻 $t$ 下 $u$ 与 $v$ 之间不存在任何可用通路，则该值取 $0$。

输入格式

从文件 cable.in 中读入数据。

• 第一行四个整数 $n, m, T, q$，分别表示节点数、光缆数、时间上界与查询次数；
• 接下来 $m$ 行，每行五个整数 $u, v, w, l, r$，表示一条连接节点 $u$ 与 $v$ 的光缆，其带宽为 $w$，检修窗口为 $[l, r]$；
• 接下来 $q$ 行，每行三个整数 $u, v, t$，表示一次查询。

输出格式

输出到文件 cable.out 中。

输出 $q$ 行，第 $i$ 行一个整数，为第 $i$ 次查询的答案。

样例

3 4 10 6
1 2 5 2 4
1 2 8 4 6
2 3 10 5 7
1 3 3 0 1
1 3 3
1 3 4
1 3 5
1 3 6
1 3 7
1 3 10

8
3
3
3
3
8

样例 1 解释

以时刻 $3$ 与时刻 $4$ 的两次查询为例。时刻 $3$：$1$ 号与 $2$ 号节点间的两条光缆中，窗口 $[2, 4]$ 的一条停用，窗口 $[4, 6]$ 的一条仍正常；$2$ 号与 $3$ 号节点间的光缆也正常。$1$ 号可经 $2$ 号到达 $3$ 号，通路上两条正常光缆带宽取较小值 $8$。时刻 $4$：窗口 $[4, 6]$ 的那条光缆停用（窗口含端点 $4$），$1$ 号与 $2$ 号节点之间不再连通，$1$ 号只能走带宽 $3$ 的直连光缆到达 $3$ 号。

2 2 5 4
1 2 4 1 4
1 2 6 0 1
1 2 0
1 2 1
1 2 2
1 2 5

4
0
6
6

样例 2 解释

时刻 $0$：窗口 $[1, 4]$ 的光缆正常，另一条在窗口 $[0, 1]$ 内停用，可用速率为 $4$。时刻 $1$：两条光缆的窗口都含端点 $1$，同时停用，$1$ 号与 $2$ 号之间没有可用光缆，答案为 $0$。时刻 $2$ 与时刻 $5$：时刻 $2$ 只有窗口 $[0, 1]$ 的光缆恢复正常，答案为 $6$；时刻 $5$ 两条光缆都正常，取 $6$。

4 4 8 4
1 2 7 1 7
2 3 5 1 7
3 4 2 1 7
1 4 9 0 0
1 4 0
1 4 1
1 4 3
1 4 8

2
9
9
9

样例 3 解释

时刻 $0$：检修尚未开始，$1$ 号可沿 $1$–$2$–$3$–$4$ 通路到达 $4$ 号，通路上带宽最小的光缆为 $2$，可用速率为 $2$。时刻 $1$、$3$：链路上三条光缆的窗口 $[1, 7]$ 含端点 $1$、在时刻 $3$ 内，全部停用；只有带宽 $9$ 的直连光缆可用，答案为 $9$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^5$，$1 \le m \le 10^5$，$1 \le q \le 10^5$，$0 \le T \le 10^9$；
• 对每条光缆：$1 \le u, v \le n$，$u \ne v$，$1 \le w \le 10^9$，$0 \le l \le r \le T$；
• 对每次查询：$1 \le u, v \le n$，$u \ne v$，$0 \le t \le T$；
• 光缆无自环；在不安排任何检修的情况下，网络是连通的。

各测试点的约束如下：

• 特殊性质 A：所有光缆的检修窗口相同，即所有 $l_e$ 相等且所有 $r_e$ 相等。
• 特殊性质 B：所有光缆的带宽相同。