题目描述

${Bovinia}$航空公司的航线连接了奶牛居住的${N}$个农场${(1<=N<=20000)}$。如同其他公司一样，所有农场当中的${K}$个被设定为枢纽。

现在${Bovinia}$航空公司提供${M}$条单项航线${(1<=M<=20000)，}$第${i}$条航线从${u_i}$号农场出发，目的地是第${v_i}$号农场，开销为${k_i}$美刀。${(1<=k_i<=10000)}$

对于每一条航线，${u_i}$和${v_i}$当中至少有一个是枢纽，两个农场间的航线最多只有${1}$条，没有起点终点相同的航线。

${Bessie}$负责管理${Bovinia}$航空公司的售票服务。不幸的是，

当她离开了几个小时去吃一些美味的干草时，奶牛们发来了

${Q(1<=Q<=50000)}$个单程的假期旅行订单，${i}$号订单希望从${a_i}$号农场飞到${b_i}$号农场。

${Bessie}$快要被订票的工作压垮了，请你帮帮她计算一下每个订单能否被满足，如果能满足，

计算满足该订单的最小花费。

为了减少输出量，你应当只输出最多可满足的订单数和最小的总花费。

为了减少输出大小，您应该只输出可能的票据请求总数，以及它们的最小总成本。注意，这个数字可能不适合${32}$位整数。

是${n}$个点${m}$条有向边，求两两之间的最短路，要求路径上必须经过编号${1\sim}$${k}$的至少一个点

输入格式

第${1}$行:整数${N}$、${M}$、${K}$和${Q}$。

第${2 . .M +1}$:第${i+1}$行包含${u_i}$、${v_i}$和${d_i}$。${(1 <= u_i, v_i <= N, u_i != v_i)}$

第${M + 2..M + K + 1}$行:每一行包含一个集线器的（范围）

第${M + K + 2..M + K + Q + 1}$行:每行两个数字，表示请求从农场${a_i}$到${b_i}$的票。${(1 <= a_i, b_i <= N, a_i != b_i)}$

输出格式

第${1}$行:整数${N}$、${M}$、${K}$和${Q}$。

第${2 . .M +1}$行:第${i+1}$行包含${u_i}$、${v_i}$和${d_i}$。${(1 <= u_i, v_i <= N, u_i != v_i)}$

第${M + 2..M + K + }$行:每一行包含一个集线器的（范围）

第${M + K + 2..M + K + Q + 1}$行:每行两个数字，表示请求从农场${a_i}$到${b_i}$的票。${(1 <= a_i, b_i <= N, a_i != b_i)}$

样例

输入样例

3 3 1 2
1 2 10
2 3 10
2 1 5
2
1 3
3 1

输出样例

1
20