Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Relations

Limits: 3s, 512 MB

Last week Mahde brought an array of n integers. Ai is the i-th integer of the array.

Each integer is positive and less than 100000.

Then he wrote m relations in his notebook. Each relation consists of 3 integers a, b, x (x= AbAa )

Then he destroys this array and he gifts you the notebook, consisting of m relations.

Now he gives you q query. Each query has 3 integers a, b, p.

In each query, you have to tell the b’th integer, if the a’th integer is p, according to the m relations which is written in his notebook. And each query is independent form another query.

Input

The first line consists of 3 integers n, m, q. here n is the array size, m is the number of relations written in his notebook, q is the number of the query. Next m lines consist of m relations a b x.

It is guaranteed that every relation is valid. Next q lines contain q query a b p.

  • 1<=n,p,m,q<=100 000
  • 1<=a,b<=n
  • And each x will be valid according to his Array .

Output

For each query print a single line consisting the b-th integer, if a-th integer is p. If it is impossible to determine this single query from these relations then print -1.

Samples

InputOutput
5 3 4
1 2 3
2 3 2
3 4 4
1 2 5
1 3 4
1 4 5
1 5 9
8
9
14
-1

Remember each query is totally independent from others.

Author
Discussion
Submit

Login to submit