Minimum Travel Time with Limited Bus Lines

In a country, there are \( n \) cities connected by \( m \) bus routes. The \( i \)-th route starts at city \( a_i \), stops at city \( b_i \), and takes \( t_i \) minutes.

Ema enjoys traveling, but she doesn't like to change buses too much. During her journey, she wishes to take at most \( k \) different bus routes.

Given multiple queries, each asking for the minimum travel time from city \( c_i \) to city \( d_i \) (using at most \( k \) bus routes), determine the answer. If it is impossible to reach the destination under the given constraint, print -1.

Note: Each bus route can be used at most once in a single trip (and each route counts as one bus line), so the total number of edges taken must be \( \le k \).

inputFormat

The first line contains four integers \( n, m, k, q \) separated by spaces, where \( n \) is the number of cities, \( m \) is the number of bus routes, \( k \) is the maximum number of bus routes Ema is willing to take, and \( q \) is the number of queries.

The next \( m \) lines each contain three integers \( a_i, b_i, t_i \), representing a bus route from city \( a_i \) to city \( b_i \) with a travel time of \( t_i \) minutes.

The next \( q \) lines each contain two integers \( c_i \) and \( d_i \), representing a query asking for the minimum travel time from city \( c_i \) to city \( d_i \) using at most \( k \) bus routes.

outputFormat

For each query output a single line containing the minimum travel time. If no valid route exists under the constraint, output -1.

sample

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

7
13
5