If you prefer easier problem, please visit here

思考题 for dw

Childish War (Hard)

Miss. Broken Tail(Wei Duan) is the Math teacher of NFLS Class 8 Junior 3.She is a kind teacher.

Miss. East(Fang Dong) is the Math teacher of NFLS Class 4 Junior 3.She is a kind teacher too.

Tail loves walking around the Xuanwu Lake to relax. So does East.

There are N islands numbered from 1 to N on Xuanwu Lake and there are M bidirectional weighted edges connecting them. It is made sure that the islands are connected and no edge has negative weight.

Tail is located at island S and East is located at island T. They decided to play a childish game.

The game has Q rounds, in each round East chooses an positive integer R and draw a circle centered at her position with the radius R1.

Tail will choose an radius R2 and draw a circle centered at her position with R2 as radius too. The score of Tail will be calculated as follows:

Let's call the number of islands included in Tail's circle but not in East's circle .Let's call the number of islands included in Tail's circle and in East's circle . Then the score of Tail's circle is where a and b are given.

For each query, find the max score of Tail's circle.

Example

Input
graph={
[1,2,2],
[2,3,2],
[1,4,2],
[4,3,2],
[1,3,3],
}

S=1 T=3 a=3 b=1
Query={
[1],
[4]
}
Output
10
4
Explain
Q1:Tail can draw a circle of radius 3 so that X=3(1,2,4) Y=1(3).
Q2:Tail can draw a circle of radius 4 so that X=0 Y=4(1,2,3,4).

Constriants

Subtask 1(50%):0<=a,b<=1e9,1<=N,M,Q<=1e5
Subtask 2(25%):0<=|a|,|b|<=1e9,1<=N,M,Q<=1000
Subtask 3(25%):0<=|a|,|b|<=1e9,1<=N,M,Q<=100000