FASTFOOD  Fast Food Restaurant
Hong Kil Dong wants to open a new fast food restaurant to make some money. The picture below describes the city where he wants to open his restaurant. The nodes are the possible locations that he can set up his new restaurant, and the edges are the length of the road connecting the two locations. You can assume that maximum five roads intersect at a single node, and that it is possible to reach all nodes from any chosen node.
There are three apartments (these three are the only places people live in) in this city, denoted A, B, and C, as shown in the picture.
Suppose he wants to open his new restaurant in location (node) 1. The shortest distances from location 1 to A, B, and C are 8, 16, and 9 respectively. These values are each larger than the shortest distances from location 4 to A, B, and C, which are 6, 7, and 3. Since people usually prefer using closer restaurants, it is better to open his restaurant in location 4.
Consider location 6. The shortest distances from location 6 to A, B, and C are 5, 3, and 5. Therefore, location 6 is better than location 1. However, when comparing with location 4, it is better regarding A and B, but worse when considering C.
Therefore, Hong Kil Dong came up with a criteria to determine whether a given location is good or bad.
Consider location p, and let the shortest distances from location p to A, B, and C be a, b, and c, respectively.
Consider another location q, and let the shortest distances from location q to A, B, and C be x, y, z, respectively.
If a>x, b>y and c>z, we say that location p is a bad location. If there is no location q that satisfies this, we say that location p is a good location.
Hong Kil Dong has chosen some candidate locations. Given the description of the city and a number of queries, determine whether each candidate location is good or bad.
Note that it is possible to open the restaurant in any of the locations, even in A, B, and C.
Input
The first line of the input is an integer N (1<=N<=100,000), denoting the number of locations. All the locations are numbered from 1N.
The second line of the input is three integers A, B, and C, denoting the location of each apartment. A, B, and C are all distinct and are between 1 and N, inclusive.
The third line of the input is M, denoting the number of roads in this city.
The next M lines give the description of each road and consist of integer X, Y, and Z (1<=Z<=10,000). X and Y are the two endpoints of this road, and Z is the length of this road. No two same roads appear in the input.
The next line is an integer T (1<=T<=10,000), denoting the number of queries.
The next T lines each consist of an integer Q (1<=Q<=N), which denote the location number.
Output
For each query, determine whether location Q is a good location or a bad location. If it is bad, output "NO" (quotes for clarity) and "YES" if it is good.
Example
Input: 9
2 5 9
15
1 2 8
1 3 5
2 4 6
2 5 8
2 6 5
3 4 6
3 9 4
4 6 4
4 9 3
5 6 3
5 7 4
6 7 2
6 9 5
7 8 7
8 9 6
2
1
2
Output: NO
YES
hide comments
lnuic:
20151230 12:31:30
Image: http://acm.bnu.edu.cn/v3/images/spoj/chain.gif


stranger:
20130706 15:11:19
plz update the picture 

sevenkplus:
20110213 14:05:58
The distance from location 1 to apartment C should be 9, not 19.


Dominik Kempa:
20110213 14:05:58
NICEDAY is a little easier due to nonconflicting values on each axis. 

[Rampage] Blue.Mary:
20110213 14:05:58
See problem NICEDAY. 

Siarhei Kulik:
20110213 14:05:58
When will we able to submit solutions for this problem? 

Hy Trường Sơn:
20110213 14:05:58
nice problem! 
Added by:  Lawl 
Date:  20110210 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  2010 KOI Final Stage Middle School & High School Division 