A lot of big storms.

Warm air and cold air don't mix very nicely – because whenever they do, storms tend to follow. Your job, as a Turbulent Location Estimator, is to track their movement.

Air currents in your area can be mapped into ~N~ nodes and ~M~ air channels. Initially, there is one warm air body at node ~X~ and one cold air body at node ~Y~. Each channel connects two distinct nodes ~A_i~ and ~B_i~ with a traverse time of ~C_i~. All channels are bidirectional and have a confined path. No two nodes will have more than one channel connecting them.

Air bodies naturally expand. So, they may intersect at nodes, or even on channels! Wherever this occurs, the present air bodies cannot pass through each other. However, if this occurs on a node that connects to other unoccupied channels, then the present air bodies can continue to spread to those channels simultaneously alongside each other.

You have been given ~Q~ queries, each asking for ~T_i~: the exact time when a storm occurs at a particular location. It is possible to reach any node from any other node. Have you got what it takes for the job?

Constraints

~1 \le X, Y, A_i, B_i \le N \le 100\,000~

~N-1 \le M \le \min\left(\frac{N(N-1)}{2}, 200\,000\right)~

~1 \le C_i \le 5\,000~

~1 \le Q \le 300\,000~

Note: It is possible to have ~X=Y~.

Subtask	Percentage	Additional Constraints
~1~	~10~	~M = \frac{N(N-1)}{2}~, ~C_i = 1~
~2~	~20~	~M = N-1~, ~X = Y~
~3~	~30~	~1 \le N \le 1\,000~, ~F_i = 1~
~4~	~40~	No additional constraints.

Input Specification

The first line contains four spaced integers: ~N~, ~M~, ~X~, and ~Y~.
The following ~M~ lines each contain three spaced integers: ~A_i~, ~B_i~, and ~C_i~.

The next line contains integer ~Q~. The following ~Q~ lines each contain two spaced integers: ~F_i~ and ~L_i~.
If ~F_i = 1~, then ~L_i~ is the number of a node ~(1 \le L_i \le N)~.
If ~F_i = 2~, then ~L_i~ is the number of a channel ~(1 \le L_i \le M)~.
Channel numbers appear in order in the input, starting at ~1~.

Output Specification

For each query, output ~T_i~ on its own line. Time starts at ~0~. If a storm does not exist at that location, output -1.
Your answer will be judged as correct if it is within an absolute error of ~0.1~.

Sample Input

7 7 1 3
1 2 6
1 5 7
2 3 6
2 6 5
3 4 1
4 5 3
5 7 8
5
1 2
1 5
1 6
2 2
2 4

Sample Output

6
-1
11
5.5
6

Explanation

The warm air body starts at node ~1~ while the cool air body starts at node ~3~. They both spread to reach node ~2~ at the same time, causing a storm there at ~T = 6~. Then, they both simultaneously spread alongside each other to node ~6~ at ~T = 11~. Note that storms occur along the entire path of channel ~4~, so we take the earliest incidence time as ~T = 6~ (rounded from a time negligibly greater than ~6~).

Meanwhile, the cool air body reaches node ~5~ first, spreading to node ~1~ and ~7~. It essentially blocks off the warm air body's path to node ~7~. Thus, both bodies of air directly collide on channel ~2~ at ~T = 5.5~.