正权连通无向图 G(n,m)G(n, m)G(n,m)，有 nnn 个节点和 mmm 条边，节点编号 1,2,⋯ ,n1,2,\cdots, n1,2,⋯,n。取图“轴点”为 ppp。有 qqq 次询问，每次询问点 xxx 到点 yyy 的所有简单路（无重复边的路）中，距离轴点最近的点。
第一行四个整数 n,m,p,qn, m, p, qn,m,p,q，表示节点数、边数、轴点和询问次数。
接下来 mmm 行，每行给出 u,v,wu, v, wu,v,w，分别表示无向边的两点和边权。
接下来 qqq 行，每行给出询问点 x,yx, yx,y。
对于每次询问，输出一行空格分隔的两个整数 z,dz, dz,d，表示点 xxx 到点 yyy 的所有简单路中，满足要求的一个点的编号（若有多个输出任意一个）和它到轴点的距离。
输入样例：
4 4 1 2 1 2 5 2 3 2 2 4 1 3 4 6 3 4 1 3
输出样例
2 5 1 0
1≤n≤2×1051 \le n \le 2\times 10^51≤n≤2×105
1≤m≤2×1051 \le m \le 2\times 10^51≤m≤2×105
1≤w≤1×1091 \le w \le 1\times 10^91≤w≤1×109
1≤p,u,v,x,y≤n1 \le p, u, v, x, y \le n1≤p,u,v,x,y≤n
1≤q≤2×1051 \le q \le 2\times 10^51≤q≤2×105