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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vpdd = vector<pdd>;
template <typename T>
void ckmin(T &a, const T &b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T &a, const T &b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <class T1, class T2>
void re(pair<T1, T2> &p);
template <class T>
void re(vector<T> &a);
template <class T, size_t SZ>
void re(array<T, SZ> &a);
template <class T>
void re(T &x) {
  cin >> x;
}
void re(double &x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg &first, Args &...rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2> &p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T> &a) {
  for (int i = 0; i < int((a).size()); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ> &a) {
  for (int i = 0; i < SZ; i++) re(a[i]);
}
}  // namespace __input
using namespace __input;
namespace __output {
template <typename T>
struct is_outputtable {
  template <typename C>
  static constexpr decltype(declval<ostream &>() << declval<const C &>(),
                            bool())
  test(int) {
    return true;
  }
  template <typename C>
  static constexpr bool test(...) {
    return false;
  }
  static constexpr bool value = test<T>(int());
};
template <
    class T, typename V = decltype(declval<const T &>().begin()),
    typename S = typename enable_if<!is_outputtable<T>::value, bool>::type>
void pr(const T &x);
template <class T,
          typename V = decltype(declval<ostream &>() << declval<const T &>())>
void pr(const T &x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2> &x);
template <class Arg, class... Args>
void pr(const Arg &first, const Args &...rest) {
  pr(first);
  pr(rest...);
}
template <class T, bool pretty = true>
void prContain(const T &x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto &a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T &x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T1, class T2>
void pr(const pair<T1, T2> &x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T, typename V, typename S>
void pr(const T &x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg &first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg &first, const Args &...rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace __output
using namespace __output;
namespace __algorithm {
template <typename T>
void dedup(vector<T> &v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <typename T>
typename vector<T>::const_iterator find(const vector<T> &v, const T &x) {
  auto it = lower_bound((v).begin(), (v).end(), x);
  return it != v.end() && *it == x ? it : v.end();
}
template <typename T>
size_t index(const vector<T> &v, const T &x) {
  auto it = find(v, x);
  assert(it != v.end() && *it == x);
  return it - v.begin();
}
template <typename I>
struct _reversed_struct {
  I &v_;
  explicit _reversed_struct(I &v) : v_{v} {}
  typename I::reverse_iterator begin() const { return v_.rbegin(); }
  typename I::reverse_iterator end() const { return v_.rend(); }
};
template <typename I>
_reversed_struct<I> reversed(I &v) {
  return _reversed_struct<I>(v);
}
}  // namespace __algorithm
using namespace __algorithm;
namespace __io {
void setIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << setprecision(15);
}
}  // namespace __io
using namespace __io;
struct edge {
  int u_xor_v;
  edge() : u_xor_v(0) {}
  edge(int _u_xor_v) : u_xor_v(_u_xor_v) {}
  int get_nbr(int u) const {
    assert(u_xor_v);
    return u ^ u_xor_v;
  }
};
template <typename Data>
struct edge_with_data : edge {
  Data data;
  edge_with_data() : edge() {}
  edge_with_data(int _u_xor_v, Data _data) : edge(_u_xor_v), data(_data) {}
};
enum TreeInputFormat { EDGE_LIST, PARENT_LIST };
template <typename Edge>
struct tree {
  int V, root;
  std::vector<std::vector<Edge>> neighbors;
  std::vector<int> parent, depth;
  tree() : V(0), root(-1) {}
  tree(int _V, int _root) : V(_V), root(_root), neighbors(V) {}
  void add_edge(int u, int v, Edge e = {}) {
    assert(0 <= u && u < V && 0 <= v && v < V);
    e.u_xor_v = u ^ v;
    neighbors[u].push_back(e);
    neighbors[v].push_back(e);
  }
  const Edge &parent_edge(int u) const {
    assert(u != root);
    return neighbors[u].front();
  }
  template <typename Function>
  void for_each_child(int u, Function fn) const {
    for (int i = u != root; i < int(neighbors[u].size()); i++)
      fn(neighbors[u][i]);
  }
  static void DefaultEdgeDataReader(__attribute((unused)) Edge &e) {}
  template <typename EdgeDataReader = void (*)(Edge &)>
  friend void re(tree &t, TreeInputFormat Format, int FirstIndex,
                 EdgeDataReader read = DefaultEdgeDataReader) {
    assert(t.V > 0);
    for (int i = 0; i < t.V - 1; i++) {
      int u, v;
      std::cin >> u, u -= FirstIndex;
      if (Format == PARENT_LIST)
        v = i + 1;
      else
        std::cin >> v, v -= FirstIndex;
      Edge e;
      read(e);
      t.add_edge(u, v, e);
    }
    t.init();
  }
  void reroot(int _root) {
    root = _root;
    init();
  }
  void init() {
    parent.resize(V), depth.resize(V);
    parent[root] = -1;
    depth[root] = 0;
    traverse(root);
  }
  void traverse(int u) {
    for (Edge e : neighbors[u]) {
      int v = e.get_nbr(u);
      if (v == parent[u]) continue;
      parent[v] = u;
      depth[v] = depth[u] + 1;
      traverse(v);
    }
  }
  static void DefaultEdgeDataWriter(__attribute((unused)) Edge &e) {}
  template <typename EdgeDataWriter = void (*)(Edge &)>
  friend void pr(const tree &t, EdgeDataWriter write = DefaultEdgeDataWriter) {
    std::cout << "{V=" << t.V << " root=" << t.root << " |";
    for (int u = 0; u < t.V; u++) {
      std::cout << " " << u << "--{";
      t.for_each_child(u, [&](Edge e) {
        std::cout << "(ch=" << e.get_nbr(u);
        write(e);
        std::cout << ")";
      });
      std::cout << "}";
    }
    std::cout << "}";
  }
};
struct union_find {
  struct node {
    int parent, rank, size;
    node(int id = 0) : parent(id), rank(0), size(1) {}
  };
  mutable std::vector<node> data;
  union_find(int SZ = 0) : data(SZ) { iota(data.begin(), data.end(), 0); }
  int find(int i) const {
    if (i != data[i].parent) data[i].parent = find(data[i].parent);
    return data[i].parent;
  }
  bool is_root(int i) const { return i == find(i); }
  node &root_node(int i) const { return data[find(i)]; }
  bool unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return false;
    if (data[a].rank < data[b].rank) std::swap(a, b);
    data[b].parent = a;
    data[a].size += data[b].size;
    if (data[a].rank == data[b].rank) data[a].rank++;
    return true;
  }
  friend void pr(const union_find &u) {
    std::cout << "{";
    bool first = 1;
    for (int i = 0; i < int(u.data.size()); i++) {
      if (u.is_root(i)) {
        if (!first)
          std::cout << ", ";
        else
          first = 0;
        std::cout << "[ " << i << " | rank=" << u.data[i].rank
                  << " size=" << u.data[i].size << " ]";
      }
    }
    std::cout << "}";
  }
};
constexpr int L = 12;
constexpr int INF = 1e9;
using E = edge;
int main() {
  setIO();
  int n, m, queries;
  re(n, m, queries);
  vvi adj(n), rev(n);
  for (int i = 0; i < m; i++) {
    int u, v;
    re(u, v);
    u--, v--;
    adj[u].push_back(v);
    rev[v].push_back(u);
  }
  struct Q {
    int start, k, index;
  };
  vector<vector<Q>> by_end(n);
  for (int query = 0; query < queries; query++) {
    int start, end, k;
    re(start, end, k);
    start--, end--, k--;
    by_end[end].push_back({start, k, query});
  }
  vi ans(queries);
  for (int end = 0; end < n; end++) {
    vb reachable(n);
    {
      queue<int> q;
      reachable[end] = true;
      q.push(end);
      while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int next : rev[cur]) {
          if (reachable[next]) continue;
          reachable[next] = true;
          q.push(next);
        }
      }
    }
    tree<E> tr(n, end);
    for (int i = 0; i < n; i++) {
      if (i == end) continue;
      if (!reachable[i]) continue;
      int next = INF;
      for (int j : adj[i]) {
        if (!reachable[j]) continue;
        ckmin(next, j);
      }
      if (next != INF) tr.add_edge(i, next);
    }
    tr.init();
    vvi anc(L, vi(n, -1));
    for (int i = 0; i < n; i++) anc[0][i] = tr.parent[i];
    for (int l = 0; l + 1 < L; l++) {
      for (int i = 0; i < n; i++) {
        if (anc[l][i] == -1) continue;
        anc[l + 1][i] = anc[l][anc[l][i]];
      }
    }
    auto solve = [&](int start, int k) {
      if (tr.depth[start] == 0) return -1;
      int cur = start;
      for (int l = 0; l < L && cur != -1; l++) {
        int second = 1 << l;
        if (second & k) {
          cur = anc[l][cur];
        }
      }
      return cur;
    };
    for (auto [start, k, index] : by_end[end]) ans[index] = solve(start, k);
  }
  for (int &i : ans) {
    if (i != -1) i++;
    ps(i);
  }
  return 0;
}
