Flaco Lombradi using high-tech instruments to oversee the new freeway system.

Fax McClad, Croneria's least politically active bounty hunter, has just witnessed a revolution on Croneria! The people of Croneria were not satisfied with the high rates imposed on the toll routes present on the Cronerian Toll Route system (even though they sometimes pay users moneys). As a result, the Committee for Charging Cronerians was disbanded and all roads were rebuilt.

The new freeway system is an automated road network with ~N~ cities, numbered from ~1~ to ~N~, and ~M~ unidirectional roads. The durability of a road can initially be up to ~10^{12}~, and decreases by ~1~ every time a vehicle passes through it. Upon reaching a durability of ~0~, the road becomes too bumpy and can no longer be used.

Fax's wingmate, Flaco, is in charge of controlling the automated road network. Every time a vehicle asks for directions, Flaco will determine a path for that vehicle using the least number of roads necessary to travel from a starting city to an ending city. In case of a tie, he picks the lexicographically least path. Obviously, the path must not contain a road with a durability of ~0~.

Suppose two paths, ~A~ and ~B~, are both of the same length. Let ~A_i~ represent the ~i^\text{th}~ city on path ~A~, and ~B_j~ represent the ~j^\text{th}~ city on path ~B~. Path ~A~ is said to be lexicographically smaller than path ~B~ if for the smallest ~x~ where ~A_x \ne B_x~, ~A_x < B_x~.

Tomorrow will be an abnormal traffic-heavy day. All vehicles will start at city ~1~ and want to go to city ~N~, but the network is so confusing that all vehicles will ask Flaco for directions. As a result, everybody will move in an entirely predictable manner. Important government officials wish to be prepared for the journey. There will be ~Q~ vehicles containing officials who will ask for a path.

Flaco only knows about the condition of the network before the day begins. Please help Flaco determine the correct paths!

Constraints

For all subtasks:

~3 \le N \le 300~

~3 \le M \le \min(30\,000, N \times (N-1))~

~1 \le Q \le 3\,000~

The durability of any road will not exceed ~10^{12}~.

~1 \le f \le 10^{15}~

Subtask	Points	Additional Constraints
1	10	~N = 3~
2	20	~f \le 300~
3	20	~M \le 300~
4	50	No additional constraints.

Input Specification

The first line contains the integers ~N~ and ~M~.

Each of the next ~M~ lines contain the description of a single uni-directional road. The first two integers, ~u~ and ~v~ ~(1 \le u,v \le N, u \ne v)~, indicate that this road connects city ~u~ to city ~v~ (and not vice versa). The third integer, ~d~, is the durability of this road. At most ~1~ road connects ~u~ to ~v~.

The next line contains the integer ~Q~.

Each of the next ~Q~ lines contain a single integer ~f~, indicating that an important vehicle will arrive in ~f^\text{th}~ place in the network. That is, ~f-1~ vehicles will have already passed in the network, reducing the durability of some roads.

Output Specification

Output ~Q~ lines, with each line describing a list of cities that Flaco should tell the vehicle to take, beginning at ~1~ and ending at ~N~, based on the path selection criteria as described above. If it is impossible to form a path, output Fail.

Sample Input

3 6
3 1 1
3 2 2
1 3 1
2 3 1
2 1 2
1 2 2
4
3
2
1
123456789

Sample Output

Fail
1 2 3
1 3
Fail