Yuki is a thrifty girl and she always tries her best to economize on money.

Yuki lives in Guangzhou, a metropolis in southern China. Everyday she needs to take metro for her study. The metro system map of Guangzhou can be considered as a graph \(G\), where there are totally \(n\) nodes as stations and \(m\) bidirectional edges with given distances linking these stations.

Yuki’s home is located nearby station \(S\) and her school is located nearby station \(T\). Also she needs to go to school \(k\) times every month, that means totally take metro \(2k\) times (\(k\) times from \(S\) to \(T\) and \(k\) times from \(T\) to \(S\), the first journey must be started at \(S\)).

Now Yuki taps Yangcheng Tong to take metro and she wants to know the minimum fares for her to pay every month.

The rules of fares in Guangzhou metro are shown as following:

• A journey shorter than 4 km (inclusive), costs ¥2.
• ¥1 is charged for every 4 km after 4 km, every 6 km after 12 km, and every 8 km after 24 km.
• If the departure and arrival station of the journey are the same, also costs ¥2.

Also Yangcheng Tong offers discounts for rides on the metro. Within each month, a 5% discount is available for the first 15 journeys and a 40% discount for all journeys beyond.

The first line contains four integers: \(n\), \(m\), \(k\) and \(q\) \((1\leq n\leq 100, 1\leq m\leq 1\ 000, 1\leq k\leq 30, 1\leq q\leq 10)\) — the number of stations, edges, times needed to go to school and the total number of queries respectively.

Each of the following \(m\) lines contains three integer \(u_i\), \(v_i\) and \(w_i\) \((1\leq u_i,v_i\leq n, 1\leq w_i\leq 20\ 000,u_i\neq v_i)\), meaning that there is a bidirectional edge from \(u_i\) to \(v_i\) with distance \(w_i\). Please be reminded that \(w_i\) is in the unit of meter.

Each of the following \(q\) lines contains two integer \(S_i, T_i\) \((S_i\neq T_i)\) — a query where \(S=S_i\) and \(T=T_i\).

For each of the queries, print one line with the result — the minimum cost Yuki needs to pay every month. The result should be accurate to two decimal places.

7 7 30 1
1 2 4000
2 3 4000
3 4 3000
4 5 6000
5 6 2000
1 7 5000
7 6 9000
1 6

201.25