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

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