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$