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 p1, p2, ... , pk, where p1 = s, pk = t, and there is a road from city pi to city pi + 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 pi < qi, where i is the minimum integer such that pi ≠ qi.

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

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

  * there is no path from sj to tj; 
  * there are paths from sj to tj, but for every such path p there is another path q from sj to tj, such that pi > qi, where i is the minimum integer for which pi ≠ qi. 



The agency would like to know for the ideal path from sj to tj the kj-th city in that path (on the way from sj to tj).

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

Input

The first line contains three integers n, m and q (2 ≤ n ≤ 3000,0 ≤ m ≤ 3000, 1 ≤ q ≤ 4·105) — the number of cities, the number of roads and the number of excursions.

Each of the next m lines contains two integers xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi), denoting that the i-th road goes from city xi to city yi. All roads are one-directional. There can't be more than one road in each direction between two cities.

Each of the next q lines contains three integers sj, tj and kj (1 ≤ sj, tj ≤ n, sj ≠ tj, 1 ≤ kj ≤ 3000).

Output

In the j-th line print the city that is the kj-th in the ideal path from sj to tj. If there is no ideal path from sj to tj, or the integer kj is greater than the length of this path, print the string '-1' (without quotes) in the j-th line.

Example

Input

7 7 5
1 2
2 3
1 3
3 4
4 5
5 3
4 6
1 4 2
2 6 1
1 7 3
1 3 2
1 3 5


Output

2
-1
-1
2
-1
import java.io.*;
import java.util.*;
import java.util.function.IntConsumer;

public class Solution333 {


    static MyScanner sc;
    private static PrintWriter out;
    static long M2 = 1_000_000_000L + 7;

    public static void main(String[] s) throws Exception {
        StringBuilder stringBuilder = new StringBuilder();
//        Random rd = new Random(4);
//        int s1 = 3000;
//        int s2 = 3000;
//        int s3 = 400000;
//        stringBuilder.append(" " + s1 + " " + s2 + " " + s3 + "  1 3000 ");
//        for (int i = 0; i < s2 - 1; i++) {
//            int r1 = i + 1;
//            int r2 = i + 2;
//            stringBuilder.append(" " + r1 + " " + r2 + " ");
//        }
//
//        for (int i = 0; i < s3; i++) {
//            int r1 = (i % 2500) + 1;
//            int r2 = r1;
//            if (r2 < 1000) {
//                r2 += rd.nextInt(700);
//            }
//            if (r2 < 2000) {
//                r2 += rd.nextInt(700);
//            }
//            if (r2 < 3000) {
//                r2 += rd.nextInt(700);
//            }
//            if (r1 == r2 || r2 > 3000) {
//                i--;
//                continue;
//            }
//            stringBuilder.append(" " + r1 + " " + r2 + " " + " 150 ");
//
//        }

        if (stringBuilder.length() == 0) {
            sc = new MyScanner(System.in);
        } else {
            sc = new MyScanner(new BufferedReader(new StringReader(stringBuilder.toString())));
        }

        out = new PrintWriter(new OutputStreamWriter(System.out));

        initData();
        solve();
        out.flush();
    }

    private static void initData() {

    }


    private static void solve() throws IOException {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        rr = new AList[n];
        rr2 = new AList[n];
        ans = new int[k];
        logTreePar = new LogTreePar(n);

        par = new int[n];
        vis22 = new int[n];
        next1 = new int[n];
        vis = new boolean[n];
        ow = new boolean[n];
        vr = new boolean[n];
        parv = new boolean[n];
        Arrays.fill(ans, -1);
        for (int l = 0; l < n; l++) {
            rr[l] = new AList();
            rr2[l] = new AList();
        }
        for (int l = 0; l < m; l++) {
            int f = sc.nextInt() - 1;
            int t = sc.nextInt() - 1;
            rr[f].add(t);
            rr2[t].add(f);
        }
        for (int l = 0; l < n; l++) {
            rr[l].sort();
            rr2[l].sort();
        }

        int[][] qq = new int[k][4];
        for (int r = 0; r < k; r++) {
            qq[r][0] = r;
            qq[r][1] = sc.nextInt() - 1;
            qq[r][2] = sc.nextInt() - 1;
            qq[r][3] = sc.nextInt() - 1;
        }
        Arrays.sort(qq, (t1, t2) -> t1[2] - t2[2]);
        int last = 0;
        for (int r = 1; r < k; r++) {
            if (qq[r][2] != qq[r - 1][2]) {
                sv(last, r, qq);
                last = r;
            }
        }
        sv(last, k, qq);
        for (int t : ans) {
            out.println(t);
        }
    }
    private static void sv(int from, int to, int[][] curQueries) {
        int root = curQueries[from][2];
        LogTreePar cur = create(root);
        cur.levels[root] = 0;
        for (int queryIndex = from; queryIndex < to; queryIndex++) {
            if (cur.levels[curQueries[queryIndex][1]] < 0) {
                continue;
            }
            int ans1;
            if ((ans1 = cur.up(curQueries[queryIndex][1], curQueries[queryIndex][3])) < 0) {
                continue;
            }
            ans[curQueries[queryIndex][0]] = ans1 + 1;
        }
    }

    private static LogTreePar create(int to) {
        logTreePar.clear();
        logTreePar.levels[to] = 0;
        fill(to);
        return logTreePar;
    }

    static LogTreePar logTreePar;
    static int[] next1;
    static int[] par;
    static boolean[] vis;
    static boolean[] parv;
    static boolean[] vr;
    static boolean[] ow;
    static int[] vis22 ;

    private static void fill(int next) {

        Arrays.fill(par, -1);
        Arrays.fill(vis, false);
        Arrays.fill(parv, false);

        vis(next, vis);

        par[next] = next;
        for (int i = 0; i < rr.length; i++) {
            if (!vis[i] || i == next) continue;
            for (int ll = 0; ll < rr[i].c; ll++) {
                int r = rr[i].data[ll];
                if (vis[r]) {
                    par[i] = r;
                    parv[r] = true;
                    break;
                }
            }
        }
        Arrays.fill(ow, false);
        Arrays.fill(vr, false);
        ow[next] = true;
        vr[next] = true;
        for (int i = 0; i < rr.length; i++) {
            if (par[i] >= 0 && !parv[i] && par[i] >= 0) {
                f(i);
            }
        }
    }

    private static void f(int r) {
        if (vr[r]) {
            return;
        }
        int l = r;
        int k = 0;
        while (!vr[l]) {
            vis22[k++] = l;
            vr[l] = true;
            l = par[l];
        }
        if (!ow[l]) return;
        vis22[k++] = l;
        for (int rt = k - 2; rt >= 0; rt--) {
            ow[vis22[rt]] = true;
            logTreePar.add(vis22[rt], vis22[rt + 1]);
        }
    }

    private static final class AList {
        int[] data;
        int c = 0;

        public AList(int n) {
            this.data = new int[Math.max(Integer.highestOneBit(n - 1) << 1, 4)];
        }

        public AList() {
            this(4);
        }

        public AList(int[] data) {
            this(data.length);
            System.arraycopy(data, 0, this.data, 0, data.length);
        }

        public void sort() {
            if (c > 0)
                Arrays.sort(data, 0, c);
        }

        public void work(IntConsumer intConsumer) {
            for (int i = 0; i < c; i++) {
                intConsumer.accept(data[i]);
            }
        }

        public void add(int k) {
            if (c == data.length) {
                data = Arrays.copyOf(data, data.length << 1);
            }
            data[c++] = k;
        }
    }


    private static void vis(int next, boolean[] vis) {
        int rr = 0;
        int wr = 0;
        next1[wr++] = next;
        vis[next] = true;
        while (rr < wr) {
            int cur = next1[rr++];
            for (int i = 0; i < rr2[cur].c; i++) {
                if (vis[rr2[cur].data[i]]) continue;
                vis[rr2[cur].data[i]] = true;
                next1[wr++] = rr2[cur].data[i];
            }
        }
    }

    private static final class LogTreePar {

        private final int[] levels;
        private final int[][] parents;


        public LogTreePar(int n) {
            levels = new int[n];
            parents = new int[n][12];
            clear();
        }

        public void clear() {
            Arrays.fill(levels, -1);
            for (int[] x : parents) {
                if (x[0] >= 0)
                    Arrays.fill(x, -1);
            }
        }

        private int up(int item, int diff) {
            int r = 0;
            int m = 1;
            while (diff > 0 && item >= 0) {
                if ((diff & m) > 0) {
                    diff -= m;
                    item = parents[item][r];
                }
                m <<= 1;
                r++;
            }
            return item;
        }


        public void  add(int item, int parent) {
            parents[item][0] = parent;
            clt(item);
        }


        protected void clt(int item) {
            levels[item] = levels[parents[item][0]] + 1;
            for (int l = 1; l < 12; l++) {
                if (parents[item][l - 1] == -1) break;
                parents[item][l] = parents[parents[item][l - 1]][l - 1];
            }
        }

        public int lca(int f, int l) {
            if (levels[f] > levels[l]) {
                return lca(l, f);
            }
            return lca1(f, up(l, levels[l] - levels[f]));
        }

        private int lca1(int f1, int f2) {
            for (int r = 11; r >= 0 && f1 != f2; r--) {
                if (parents[f1][r] != parents[f2][r]) {
                    f1 = parents[f1][r];
                    f2 = parents[f2][r];
                }
            }
            return f1 == f2 ? f1 : parents[f1][0];
        }
    }

    static AList[] rr;
    static AList[] rr2;
    static int[] ans;


    private static void solveT() throws IOException {
        int t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }


    private static long gcd(long l, long l1) {
        if (l > l1) return gcd(l1, l);
        if (l == 0) return l1;
        return gcd(l1 % l, l);
    }

    private static long pow(long a, long b, long m) {
        if (b == 0) return 1;
        if (b == 1) return a;
        long pp = pow(a, b / 2, m);
        pp *= pp;
        pp %= m;
        return (pp * (b % 2 == 0 ? 1 : a)) % m;
    }


    static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        MyScanner(BufferedReader br) {
            this.br = br;
        }

        public MyScanner(InputStream in) {
            this(new BufferedReader(new InputStreamReader(in)));
        }

        void findToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }

        String next() {
            findToken();
            return st.nextToken();
        }

        Integer[] nab(int n) {
            Integer[] k = new Integer[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        int[] na(int n) {
            int[] k = new int[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        long[] nl(int n) {
            long[] k = new long[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.nextLong();
            }
            return k;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int fi() {
            String t = next();
            int cur = 0;
            boolean n = t.charAt(0) == '-';
            for (int a = n ? 1 : 0; a < t.length(); a++) {
                cur = cur * 10 + t.charAt(a) - '0';
            }
            return n ? -cur : cur;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }


}