You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

Background

大卫为了救露西葬身荒坂。法尔科要完成大卫的嘱托，带露西逃离。

Description

法尔科可能会去到 $n$ 个地点，共有 $m$ 条路将其联通，每条路都是双向联通的。露西通过黑客技术得到了信息，荒坂公司为了抓捕他们，在这 $m$ 条路上设置了不同程度的拦截 $w_i$。法尔科的车是有耐久的，不可能随便冲关。具体来说，法尔科每经过一条路，其车的耐久就会减少该路对应的 $w_i$。法尔科车子的耐久上限为 $C$。这样子可能很难冲出重围，所以法尔科提前联系好了 $k$ 个地点的维修商（$1$ 到 $k$），到达该地点后，车子的耐久度恢复至上限 $C$。 现在请你帮帮法尔科，他有 $q$ 次询问，问从维修站 $a$ 到达维修站 $b$ 所需要的最小 $C$。

Input Format

输入格式

第一行给定四个整数 $n，m，k，q$。 接下来 $m$ 行，每行三个整数，$u，v，w$ 表示 $u$ 与 $v$ 之间有一条拦截程度为 $w$ 的路。 接下来 $q$ 行，每行两个整数 $a，b$ 表示询问的地点。保证 $a$ 不等于 $b$，且 $a，b \leqslant k$

Output Format

输出格式

输出 $q$ 行，每行一个整数 $C$ ,表示该次询问能够到达所需的最小 $C$。

Sample

样例

9 11 3 2
1 3 99
1 4 5
4 5 3
5 6 3
6 4 11
6 7 21
7 2 6
7 8 4
8 9 3
9 2 57
9 3 2
3 1
2 3

38
15

Hint

数据范围

$1 \leqslant k \leqslant n \leqslant 10^5$

$1 \leqslant m, q \leqslant 2\times 10^5$

$1 \leqslant w \leqslant 10^9$