#include <bits/stdc++.h> using namespace std; const int N = 2005, M = 5005; int n, m, Q, type, st, ed, pa[13][N][N]; vector<int> g[N], h[N]; bool go[N][N], vis[N], lmt[N][N], mark[N]; void dfs(int u) { vis[u] = go[u][st] = true; for (int v : h[u]) if (!vis[v]) dfs(v); } int trans(int x, int lst) { return ((x ^ lst) % n) + 1; } bool dfs2(int u) { // if (u == 1 && ed == 1) // cout << "check" << endl; if (mark[u]) return lmt[u][ed]; if (vis[u]) { mark[u] = true; return lmt[u][ed] = false; } vis[u] = true; if (u == ed) return mark[u] = lmt[u][ed] = true; if (!go[u][ed]) { // if (u == 96 && ed == 1) // cout << "check" << endl; mark[u] = true; return lmt[u][ed] = false; } lmt[u][ed] = dfs2(pa[0][u][ed]); mark[u] = true; return lmt[u][ed]; } int jump(int u, int v, int len) { for (int k = 10; k >= 0; k--) if (len & (1 << k)) u = pa[k][u][v]; return u; } int main() { #ifndef ONLINE_JUDGE freopen("data.in", "r", stdin); freopen("data.out", "w", stdout); #endif cin >> n >> m >> Q >> type; int u, v; for (int i = 1; i <= m; i++) scanf("%d%d", &u, &v), g[u].push_back(v), h[v].push_back(u); for (st = 1; st <= n; st++) { memset(vis, 0, sizeof(vis)); dfs(st), sort(g[st].begin(), g[st].end()); } for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i != j) { if (go[i][j]) for (int v : g[i]) { if (go[v][j]) pa[0][i][j] = v; break; } } for (ed = 1; ed <= n; ed++) // end point { memset(vis, 0, sizeof(vis)); memset(mark, 0, sizeof(mark)); for (int j = 1; j <= n; j++) if (ed != j && !vis[j]) dfs2(j); } for (int k = 1; k <= 10; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) pa[k][i][j] = pa[k - 1][pa[k - 1][i][j]][j]; int k, lst = 1; while (Q--) { scanf("%d%d%d", &st, &ed, &k); // cout << st << ' ' << ed << ' ' << k << endl; if (type) st = trans(st, lst), ed = trans(ed, lst), k = trans(k, lst); k--; // cout << lst << ' ' << st << ' ' << ed << ' ' << k << endl; if (!go[st][ed] || !lmt[st][ed]) { // cout << go[st][ed] << ' ' << lmt[st][ed] << endl; cout << go[st][ed] << ' ' << lmt[st][ed] << ' '; puts("-1"), lst = 1; continue; } int u = jump(st, ed, k); if (!u) { puts("-1"), lst = 1; continue; } printf("%d\n", lst = u); } return 0; }