Although Pharaoh Tomeses LXVII managed to conserve water through the droughts and bring prosperity to Egypt, Maged is not happy about his prediction market money-making schemes, such as betting on himself saying absurd things in speeches and then saying them. Thus, Maged brings a gang of friends and overthrows Tomeses, becoming the new supreme leader of Egypt. As part of one of his first policies, he would like to take control over one of the most important resources - the river Nile.

The river can be modelled as a set of many junctions which are connected by streams. The head of the river starts at a junction labelled with an integer ID 0. Water flows directionally, from a given junction to downstream to other junctions. Once a stream branches off at a junction, it remains separate and never merges back into another part of the system. Each stream of river also has an integer associated with it - the number of people which rely on this section of river as a water source.

Maged would like more people to relocate closer to the head of the river, and to do this he will put exactly one blockade at one junction in the river. This causes water to stop flowing to any junctions downstream of this junction, which causes all people who relied on those sections of river for water to relocate.

Maged has several possible numbers he's thinking of for the amount of people he'd like to relocate, and needs to find the best possible junction to blockade for each of these numbers. For a given query of wanting to relocate ~n~ people, he defines the "best" junction as the junction to blockade which will cause ~c~ people to relocate, where ~c \geq n~, and ~c~ is minimized. If multiple junctions satisfy this, the junction with the lowest ID is preferred. Can you help him find these junctions?

Input

The first line consists of an integer ~n~ ~(1 \leq n \leq 10^5)~, the number of junctions in the river. Junctions are labelled from ~0~ to ~n-1~.

The next ~n-1~ lines consist of 3 integers ~s_n~ ~e_n~ ~p~, representing a unidirectional section of the river. The first value is the start junction, the second value is the end junction, and the last value is the number of people who rely on that section of river for water. ~1 \leq p \leq 10^4~.

The next line consists of an integer ~x~ ~(1 \leq x \leq 10^4)~, the number of queries Maged has.

The next ~x~ lines consist of a single integer ~q~ ~(1 \leq q \leq 10^9)~, the number of people Maged would like to relocate.

Output

For each query ~q~, output a single integer on a new line, the best junction to blockade. If it is impossible to relocate at least ~q~ people, output -1 for this query.

Examples

Input 1

5
0 1 1
1 2 5
1 3 3
3 4 10
2
10
16

Output 1

3
1

The river can be visualized with the image below.

In the first query, the optimal junction to blockade is 3, as it will cause exactly ~10~ people to relocate.

In the second query, the optimal junction to blockade is 1, as it will cause ~5+3+10=18~ people to relocate.

Input 2

8
0 1 4
0 5 1
1 2 5
2 3 7
2 4 3
5 6 4
6 7 10
3
10
15
100

Output 2

2
1
-1

The river can be visualized with the image below.

In the first query, blocking junctions ~2~ and ~6~ both would cause exactly ~10~ people to relocate, but junction ~2~ is preferred as it has the lower ID.

In the second query, blocking node ~1~ causes ~5 + 7 + 3 = 15~ people to relocate.

In the third query, there is no node we can block that can cause at least ~100~ people to relocate.