Paging Signal Transmission

Freda has built two pagers so she can communicate quickly with Rainbow. There are \(N\) houses and \(M\) bidirectional optical cables connecting them. Each cable connects two houses and the pager signal can only be relayed along these cables. The signal takes \(t\) units of time to travel along any cable.

It is known that the network of \(N\) houses is connected. Furthermore, the \(M\) cables satisfy one of the following conditions:

• Type A: The cables do not form any cycle (in other words, there are exactly \(N-1\) cables).
• Type B: The cables form exactly one cycle (i.e. there are exactly \(N\) cables).
• Type C: Each cable belongs to exactly one cycle.

Freda now wants to perform \(Q\) experiments. In each experiment, she selects two houses and wishes to know the minimum time required for the pager signal to travel between them. Since the signal traverses each cable in \(t\) units of time, the minimum time is \(t\) times the number of cables in the shortest path between the two houses.

Your task is to help them determine this minimum transmission time for each query.

inputFormat

The first line contains four integers (N), (M), (Q), and (t), where (N) is the number of houses, (M) is the number of cables, (Q) is the number of queries, and (t) is the time it takes for a signal to pass through one cable.

Then (M) lines follow, each with two integers (u) and (v) indicating that there is a cable connecting house (u) and house (v).

After that, (Q) lines follow, each containing two integers (s) and (e), representing a query that asks for the minimum transmission time between house (s) and house (e).

It is guaranteed that the network of houses is connected.

outputFormat

For each query, output a single line containing the minimum transmission time between the two specified houses.

sample

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

10
5