#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=2e3+7; const int LB=12; int n,m,q,tp; vector<int> E[maxn]; int U[maxn]; int V[maxn]; int F[maxn][maxn][LB]; bool vis[maxn]; void DFS(int u){ // cout<<u<<endl; vis[u]=1; for(auto v:E[u])if(!vis[v])DFS(v); }//求出所有可以到达 t 的点 void Set(int ST[maxn][LB],int t){ for(int i=0;i<=n;i++)ST[i][0]=0; for(int i=1;i<=m;i++)if(vis[U[i]]&&vis[V[i]])ST[U[i]][0]=min(ST[U[i]][0],V[i]); ST[t][0]=0; for(int j=1;j<LB;j++)for(int i=0;i<=n;i++)ST[i][j]=ST[ST[i][j-1]][j-1]; }//预处理 signed main(){ cin>>n>>m>>q>>tp; for(int i=1;i<=m;i++)cin>>U[i]>>V[i],E[V[i]].push_back(U[i]); for(int t=1;t<=n;t++){ for(int i=1;i<=n;i++)vis[i]=0; DFS(t);Set(F[t],t); cout<<"! "<<t<<endl; } int lst=1; while(q--){ int s,t,k; cin>>s>>t>>k; s^=(lst*tp);t^=(lst*tp);k^=(lst*tp); s=s%n+1;t=t%n+1;k=k%n+1; cout<<s<<" "<<t<<" "<<k<<endl; if(!F[t][s][0]){ //不可达 // cerr<<"INACCESSABLE"<<endl; lst=1,cout<<-lst<<endl; continue; } if(F[t][F[t][s][LB-1]][LB-1]){ //进环 // cerr<<"CYCLE"<<endl; lst=1,cout<<-lst<<endl; continue; } k--; for(int i=LB-1;i>=0;i--)if(k&(1<<i))s=F[t][s][i]; if(!s){ // cerr<<"THE LENGTH OF THE PATH IS NOT ENOUGH"<<endl; lst=1,cout<<-lst<<endl; continue; } lst=s; cout<<lst<<endl; } }