There are n cities in Berland. Some pairs of them are connected with m directed roads. One can use only these roads to move from one city to another. There are no roads that connect a city to itself. For each pair of cities (x, y) there is at most one road from x to y.

A path from city s to city t is a sequence of cities p₁, p₂, ... , p_k, where p₁ = s, p_k = t, and there is a road from city p_i to city p_i + 1 for each i from 1 to k - 1. The path can pass multiple times through each city except t. It can't pass through t more than once.

A path p from s to t is ideal if it is the lexicographically minimal such path. In other words, p is ideal path from s to t if for any other path q from s to t p_i < q_i, where i is the minimum integer such that p_i ≠ q_i.

There is a tourist agency in the country that offers q unusual excursions: the j-th excursion starts at city s_j and ends in city t_j.

For each pair s_j, t_j help the agency to study the ideal path from s_j to t_j. Note that it is possible that there is no ideal path from s_j to t_j. This is possible due to two reasons:

• there is no path from s_j to t_j;
• there are paths from s_j to t_j, but for every such path p there is another path q from s_j to t_j, such that p_i > q_i, where i is the minimum integer for which p_i ≠ q_i.

The agency would like to know for the ideal path from s_j to t_j the k_j-th city in that path (on the way from s_j to t_j).

For each triple s_j, t_j, k_j (1 ≤ j ≤ q) find if there is an ideal path from s_j to t_j and print the k_j-th city in that path, if there is any.