Souvlakia

Mr. Papadopoulos was fired from the restaurant where he worked and decided to open a souvlaki place for home delivery in the "Modern Residences" neighborhood. He wants to choose the best location for his store. The nodes of the following diagram show his possible choices.

He can choose to rent a store in one of the nine positions where potential stores are available for rent. However, apartments with residents exist only in three of these positions (A, B, or Γ, or positions ~2~, ~5~, and ~9~). The possible points are connected by roads as shown in the diagram with the corresponding distances.

Customers tend to shop from the nearest store. If he chooses position ~1~, then the minimum distances from A, B, and Γ are respectively ~4~, ~8~, and ~9~, while if he chooses position ~7~, the corresponding minimum distances are ~13~, ~9~, and ~12~. If he chooses position ~6~, then the minimum distances from A, B, and Γ are respectively ~9~, ~7~, and ~4~, which are all better than those of position ~7~ but not better than those of position ~1~ (position ~1~ is better in terms of distance from ~A~).

Therefore, in order to choose the most suitable location for the store, Mr. Papadopoulos decides to examine candidate positions and exclude those that are inferior to another position in terms of the three distances from A, B, and Γ. Specifically, a position ~p~, with minimum distances ~a~, ~b~, ~c~ from A, B, and Γ respectively, is excluded if there exists a position ~q~, with minimum distances ~x~, ~y~, ~z~ from A, B, and Γ, where ~a > x~, ~b > y~, and ~c > z~.

Problem:

Develop a program in one of the IOI languages that, after reading the lengths of the roads connecting the positions of the potential stores and the positions A, B, Γ where residents exist, will read a sequence of positions and respond whether each of them is a candidate location for the store or not, based on the above rule. There may be more than one possible position questions, and questions can also be asked for positions A, B, and Γ.

Input File:

The input files, named souvlakia.in, are text files with the following structure: The first line contains two integers separated by a single space: an integer ~N\;(3 \le N \le 100.000)~ representing the number of candidate positions, and an integer ~M\;(3 \le M \le 400.000)~ representing the number of roads connecting these positions. Each of the next ~M~ lines contains three integers separated between them by a single space, representing a road: the first two correspond to the two ends of the road, and the third represents the length of the road ~d\;(1 \le d \le 20.000)~. Then, on line ~M + 2~, there are four integers separated by a single space: the first three correspond to the positions A, B, and Γ, and the fourth integer ~L\;(1 \le L \le 50.000)~ represents the number of questions that follow. Each of the next ~L~ lines contains an integer corresponding to a candidate position to be checked.

All roads are considered two-way. Also, there will be no two different roads with the same endpoints.

Output File:

The output files named souvlakia.out are text files with the following structure: They contain ~L~ lines, each of which contains the answer to one of the questions, in the same order. Each answer will be "YES" if Mr. Papadopoulos can open his store at the corresponding position, otherwise "NO".

Example of Input - Output Files:

STDIN (souvlakia.in)

9 15
1 2 4
2 5 4
1 3 8
2 4 7
2 6 11
3 4 1
4 6 2
5 6 7
3 9 1
4 9 6
6 9 4
8 9 2
6 7 14
5 7 9
8 7 10
2 5 9 9
1
2
3
4
5
6
7
8
9

STDOUT (souvlakia.out)

YES
YES
YES
YES
YES
YES
NO
NO
YES

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 1 sec.
Maximum available memory: 64 MB.

For test cases worth ~30~%, of the total points, it will be: ~N \le 2000~, ~M \le 15.000~ and ~L \le 1000~