#include<iostream> #include<vector> #include<bitset> #include<ctime> #define timeMS (clock()*1000/CLOCKS_PER_SEC) using namespace std; inline int read(){ int i=getchar(),r=0; while(i<'0'||i>'9')i=getchar(); while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar(); return r; } const int N=2010,M=5010,LG=12; int n,m,q,t; int head[N<<1],to[M<<1],nex[M<<1],edge; inline void insert(int u,int v){ edge++; to[edge]=v; nex[edge]=head[u]; head[u]=edge; } int bel[N],low[N],dfn[N],stk[N],top; vector<int>bc[N]; bool in_stk[N]; bitset<N>accb[N],acc[N]; int tarjan(int nd){ dfn[nd]=low[nd]=++dfn[0]; stk[++top]=nd; in_stk[nd]=true; for(int i=head[nd];i;i=nex[i])if(!bel[to[i]]){ if(in_stk[to[i]])low[nd]=min(low[nd],dfn[to[i]]); else tarjan(to[i]),low[nd]=min(low[nd],low[to[i]]); } if(low[nd]==dfn[nd]){ while(stk[top]!=nd)in_stk[stk[top]]=false,bel[stk[top--]]=nd; in_stk[stk[top]]=false,bel[stk[top--]]=nd; } } int deg[N<<1],que[N],front,back; void topo(){ for(int i=1;i<=n;i++)if(!deg[i+n])que[++back]=i+n; while(front<back){ int nd=que[++front]; for(int i=head[nd];i;i=nex[i]){ if(!--deg[to[i]])que[++back]=to[i]; } } for(int i=n;i;i--){ accb[i][i]=true; for(int e=head[i+n];e;e=nex[e])accb[i]|=accb[to[e]-n]; } } void init(){ cin>>n>>m>>q>>t; for(int i=1;i<=m;i++){ int u=read(),v=read(); insert(u,v); } for(int i=1;i<=n;i++)if(!bel[i])tarjan(i); for(int i=1;i<=n;i++)bc[bel[i]].emplace_back(i); for(int i=1;i<=n;i++)for(int x:bc[i]){ for(int e=head[x];e;e=nex[e])insert(i+n,bel[to[e]]+n),deg[bel[to[e]]+n]++; } topo(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ acc[i][j]=accb[bel[i]][bel[j]]; } } } int fa[N][N][LG];//目标为 i 下 j 的下一步 inline int kfa(int i,int nd,int k){ for(int j=0;k;k>>=1,j++)if(k&1)nd=fa[i][nd][j]; return nd; } int main(){ // freopen("path.in","r",stdin); // freopen("path.out","w",stdout); init(); for(int i=1;i<=n;i++){//枚举目标 for(int j=1;j<=n;j++)if(acc[j][i]&&i!=j){ int mn=n+1; for(int e=head[j];e;e=nex[e])if(acc[to[e]][i])mn=min(mn,to[e]); if(mn>n)continue; fa[i][j][0]=mn; } for(int l=1;l<LG;l++){ for(int j=1;j<=n;j++)fa[i][j][l]=fa[i][fa[i][j][l-1]][l-1]; } } int lans=1; while(q--){ int u,v,k; // if(t)u=(read()^lans*t)%n+1,v=(read()^lans*t)%n+1,k=(read()^lans*t)%n+1; // else u=read(),v=read(),k=read(); // if(kfa(v,u,n)!=0||kfa(v,u,k-1)==0){printf("-1\n");lans=1;continue;} // lans=kfa(v,u,k-1); // printf("%d\n",lans); } // cerr<<timeMS; return 0; }