You're given a simple, undirected, connected, weighted graph with n nodes and m edges.

Nodes are numbered from 1 to n. There are exactly k centrals (recharge points), which are nodes 1, 2, …, k.

We consider a robot moving into this graph, with a battery of capacity c, not fixed by the constructor yet. At any time, the battery contains an integer amount x of energy between 0 and c inclusive.

Traversing an edge of weight w_i is possible only if x ≥ w_i, and costs w_i energy points (x := x - w_i).

Moreover, when the robot reaches a central, its battery is entirely recharged (x := c).

You're given q independent missions, the i-th mission requires to move the robot from central a_i to central b_i.

For each mission, you should tell the minimum capacity required to acheive it.

Input

The first line contains four integers n, m, k and q (2 ≤ k ≤ n ≤ 10^5 and 1 ≤ m, q ≤ 3 ⋅ 10^5).

The i-th of the next m lines contains three integers u_i, v_i and w_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i, 1 ≤ w_i ≤ 10^9), that mean that there's an edge between nodes u and v, with a weight w_i.

It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes) and connected.

The i-th of the next q lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ k, a_i ≠ b_i).

Output

You have to output q lines, where the i-th line contains a single integer : the minimum capacity required to acheive the i-th mission.

Examples

Input


10 9 3 1
10 9 11
9 2 37
2 4 4
4 1 8
1 5 2
5 7 3
7 3 2
3 8 4
8 6 13
2 3


Output


12


Input


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


Output


38
15

Note

In the first example, the graph is the chain 10 - 9 - 2^C - 4 - 1^C - 5 - 7 - 3^C - 8 - 6, where centrals are nodes 1, 2 and 3.

For the mission (2, 3), there is only one simple path possible. Here is a simulation of this mission when the capacity is 12.

  * The robot begins on the node 2, with c = 12 energy points. 
  * The robot uses an edge of weight 4.
  * The robot reaches the node 4, with 12 - 4 = 8 energy points. 
  * The robot uses an edge of weight 8.
  * The robot reaches the node 1 with 8 - 8 = 0 energy points. 
  * The robot is on a central, so its battery is recharged. He has now c = 12 energy points. 
  * The robot uses an edge of weight 2.
  * The robot is on the node 5, with 12 - 2 = 10 energy points. 
  * The robot uses an edge of weight 3.
  * The robot is on the node 7, with 10 - 3 = 7 energy points. 
  * The robot uses an edge of weight 2.
  * The robot is on the node 3, with 7 - 2 = 5 energy points. 
  * The robot is on a central, so its battery is recharged. He has now c = 12 energy points. 
  * End of the simulation. 



Note that if value of c was lower than 12, we would have less than 8 energy points on node 4, and we would be unable to use the edge 4 ↔ 1 of weight 8. Hence 12 is the minimum capacity required to acheive the mission.

—

The graph of the second example is described here (centrals are red nodes):

<image>

The robot can acheive the mission (3, 1) with a battery of capacity c = 38, using the path 3 → 9 → 8 → 7 → 2 → 7 → 6 → 5 → 4 → 1

The robot can acheive the mission (2, 3) with a battery of capacity c = 15, using the path 2 → 7 → 8 → 9 → 3
#include <bits/stdc++.h>
using namespace std;
struct Edge {
  int x, y;
  long long val;
} e[3 * 100055];
bool cmp(Edge x1, Edge x2) { return x1.val < x2.val; }
int head[100055], to[6 * 100055], nex[6 * 100055];
long long w[6 * 100055];
int edge;
inline void addEdge(int x, int y, long long z) {
  to[++edge] = y, w[edge] = z, nex[edge] = head[x], head[x] = edge;
  to[++edge] = x, w[edge] = z, nex[edge] = head[y], head[y] = edge;
}
int n, m, k, q;
void init() {
  for (int i = 1; i <= n; i++) head[i] = 0;
  edge = 0;
}
bool vis[100055];
long long d[100055];
struct node {
  int x;
  long long val;
  node(int x, long long val) : x(x), val(val) {}
  friend bool operator<(node x1, node x2) { return x1.val > x2.val; }
};
priority_queue<node> que;
int pre[100055];
int findd(int x) {
  if (pre[x] == x) return x;
  return pre[x] = findd(pre[x]);
}
long long f[100055][18];
int g[100055][18];
int dep[100055];
int N;
void dfs(int u, int fa) {
  for (int i = 1; i <= N; i++) {
    g[u][i] = g[g[u][i - 1]][i - 1];
    f[u][i] = max(f[u][i - 1], f[g[u][i - 1]][i - 1]);
  }
  for (int i = head[u]; i; i = nex[i]) {
    int v = to[i];
    if (v == fa) continue;
    dep[v] = dep[u] + 1;
    g[v][0] = u;
    f[v][0] = w[i];
    dfs(v, u);
  }
}
inline long long lca(int x, int y) {
  if (dep[x] > dep[y]) swap(x, y);
  long long ans = 0;
  for (int i = N; i >= 0; i--) {
    if (dep[g[y][i]] >= dep[x]) {
      ans = max(ans, f[y][i]);
      y = g[y][i];
    }
  }
  if (x == y) return ans;
  for (int i = N; i >= 0; i--) {
    if (g[x][i] != g[y][i]) {
      ans = max(f[x][i], ans);
      ans = max(f[y][i], ans);
      x = g[x][i];
      y = g[y][i];
    }
  }
  if (x != y) ans = max(ans, f[x][0]), ans = max(ans, f[y][0]);
  return ans;
}
int main() {
  cin >> n >> m >> k >> q;
  int x, y, z;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &x, &y, &z);
    addEdge(x, y, z);
    e[i].x = x, e[i].y = y, e[i].val = z;
  }
  for (int i = k + 1; i <= n; i++) d[i] = 0x7f7f7f7f7f7f7f7f;
  for (int i = 1; i <= k; i++) que.push(node(i, 0));
  while (que.size()) {
    int u = que.top().x;
    que.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (int i = head[u]; i; i = nex[i]) {
      int v = to[i];
      if (d[v] > d[u] + w[i]) {
        d[v] = d[u] + w[i];
        que.push(node(v, d[v]));
      }
    }
  }
  for (int i = 1; i <= m; i++) e[i].val += (d[e[i].x] + d[e[i].y]);
  sort(e + 1, e + 1 + m, cmp);
  init();
  for (int i = 1; i <= n; i++) pre[i] = i;
  for (int i = 1; i <= m; i++) {
    x = e[i].x;
    int xx = findd(x);
    y = e[i].y;
    int yy = findd(y);
    if (xx != yy) {
      pre[xx] = yy;
      addEdge(x, y, e[i].val);
    }
  }
  N = ceil(log2(n));
  dep[1] = 1;
  dfs(1, 0);
  while (q--) {
    scanf("%d%d", &x, &y);
    printf("%lld\n", lca(x, y));
  }
  return 0;
}
