Problem: You are given a connected graph with N vertices and M edges. The vertices are numbered 1 to N. The i-th edge is an undirected edge of length C_i connecting Vertex A_i and Vertex B_i.

Additionally, an odd number MOD is given.

You will be given Q queries, which should be processed. The queries take the following form:

* Given in the i-th query are S_i, T_i and R_i. Print `YES` if there exists a path from Vertex S_i to Vertex T_i whose length is R_i modulo MOD, and print `NO` otherwise. A path may traverse the same edge multiple times, or go back using the edge it just used.



Here, in this problem, the length of a path is NOT the sum of the lengths of its edges themselves, but the length of the first edge used in the path gets multiplied by 1, the second edge gets multiplied by 2, the third edge gets multiplied by 4, and so on. (More formally, let L_1,...,L_k be the lengths of the edges used, in this order. The length of that path is the sum of L_i \times 2^{i-1}.)

Constraints

* 1 \leq N,M,Q \leq 50000
* 3 \leq MOD \leq 10^{6}
* MOD is odd.
* 1 \leq A_i,B_i\leq N
* 0 \leq C_i \leq MOD-1
* 1 \leq S_i,T_i \leq N
* 0 \leq R_i \leq MOD-1
* The given graph is connected. (It may contain self-loops or multiple edges.)

Input

Input is given from Standard Input in the following format:


N M Q MOD
A_1 B_1 C_1
\vdots
A_M B_M C_M
S_1 T_1 R_1
\vdots
S_Q T_Q R_Q


Output

Print the answers to the i-th query in the i-th line.

Examples

Input

3 2 2 2019
1 2 1
2 3 2
1 3 5
1 3 4


Output

YES
NO


Input

6 6 3 2019
1 2 4
2 3 4
3 4 4
4 5 4
5 6 4
6 1 4
2 6 1110
3 1 1111
4 5 1112


Output

YES
NO
NO


Input

1 2 3 25
1 1 1
1 1 2
1 1 13
1 1 6
1 1 14


Output

YES
YES
YES


Input

10 15 10 15
1 2 1
2 3 6
3 4 6
2 5 1
5 6 1
4 7 6
1 8 11
2 9 6
5 10 11
9 10 11
3 6 1
2 5 1
2 7 11
9 10 11
5 6 11
1 3 5
9 8 3
7 7 7
7 10 13
4 1 10
9 3 12
10 10 14
9 2 1
6 6 5
8 8 4


Output

YES
NO
NO
NO
NO
NO
NO
YES
YES
NO

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#include <type_traits>
using namespace std;

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(),x.end()
auto& errStream=cerr;
#ifdef LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"(";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<")";
}

ll read(){
	ll i;
	scanf("%"  SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

template<class T>
void print(const vector<T>&v){
	REP(i,v.size())
		print(v[i],i==int(v.size())-1?1:2);
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

constexpr ll TEN(int n){
	return n==0?1:TEN(n-1)*10;
}

template<class T>
vector<T> Uniqued(const vector<T>&vv){
	auto v(vv);
	sort(ALL(v));
	v.erase(unique(ALL(v)),v.end());
	return v;
}
template<class T>
void MakeUniqued(vector<T>&v){
	sort(ALL(v));
	v.erase(unique(ALL(v)),v.end());
}

int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}

int lcm(int a,int b){
	return a/gcd(a,b)*b;
}

int extgcd(int a,int b,int&x,int&y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}else{
		int g=extgcd(b,a%b,y,x);
		y-=a/b*x;
		return g;
	}
}

struct Edge{
	int to,cost;
};

struct Query{
	int s,t,v;
};

struct VerySlow{
	int n;
	vector<vector<Edge>> g;
	int p;
	VerySlow(const vector<vector<Edge>>&gg,const int pp):
	n(gg.size()),g(gg),p(pp){
	}
	static const int Size=2019;
	bool vis[Size][Size];
	int gV,gD;
	bool dfs(int v,int d){
		if(v==gV&&d==gD)
			return true;
		if(vis[v][d])
			return false;
		vis[v][d]=true;
		for(auto e:g[v])
			if(dfs(e.to,(d*2+e.cost)%p))
				return true;
		return false;
	}
	bool Query(int src,int dst,int v){
		ZERO(vis);
		gV=src;
		gD=v;
		return dfs(dst,0);
	}
};

struct Slow{
	int n;
	vector<vector<Edge>> g;
	int p;
	int s;
	vi dep,ord;
	Slow(const vector<vector<Edge>>&gg,const int pp):
	n(gg.size()),g(gg),p(pp){
		vi pow2{1};
		while(1){
			int nx=pow2.back()*2%p;
			if(nx==1)break;
			pow2.PB(nx);
		}
		s=pow2.size();
		dep.assign(n*s,-1);
		ord.assign(n*s,-1);
		
		vi st;
		const auto Reach=[&](int i,int j,int d){
			if(dep[i*s+j]!=-1)
				return;
			dep[i*s+j]=d;
			st.PB(i*s+j);
		};
		Reach(0,0,0);
		while(!st.empty()){
			int w=st.back();st.pop_back();
			int i=w/s,j=w%s;
			for(auto e:g[i]){
				int nx=(dep[w]+e.cost*pow2[j])%p;
				Reach(e.to,(j+1)%s,nx);
			}
		}
		
		REP(i,n)REP(j,s)for(auto e:g[i])if(dep[i*s+j]!=-1){
			int w=(dep[i*s+j]+e.cost*pow2[j]-dep[e.to*s+(j+1)%s])%p;
			if(w<0)w+=p;
			p=gcd(w,p);
		}
		REP(i,n)REP(j,s)if(dep[i*s+j]!=-1)
			dep[i*s+j]%=p;
	}
	bool Query(int src,int dst,int v){
		if(dep[src*s]!=-1)
			v=(v+dep[src*s])%p;
		else
			v=(v*2+dep[src*s+1])%p;
		REP(j,s)if(dep[dst*s+j]==v)
			return true;
		return false;
	}
};

struct UnionFind{
	vi rank,par;
	void Init(int n){
		rank.assign(n,0);
		par.assign(n,-1);
	}
	int Find(int i){
		return par[i]==-1?i:(par[i]=Find(par[i]));
	}
	bool Same(int a,int b){
		return Find(a)==Find(b);
	}
	bool Unite(int a,int b){
		a=Find(a);
		b=Find(b);
		if(a==b)
			return false;
		if(rank[a]<rank[b])
			swap(a,b);
		par[b]=a;
		if(rank[a]==rank[b])
			rank[a]++;
		return true;
	}
};

struct Solver{
	int n;
	vector<vector<Edge>> g;
	int p;
	int ord,q,gcd_pq,inv_q,len;
	vi lg2;
	UnionFind uf;
	Solver(const vector<vector<Edge>>&gg,const int pp):
	n(gg.size()),g(gg),p(pp){
		{
			int base=g[0][0].cost;
			REP(i,n)
				for(auto e:g[i])
					p=gcd(p,3*(e.cost-base)%p+p);
			REP(i,n)
				for(auto&e:g[i])
					e.cost%=p;
		}
		if(p==1)return;
		if(p%3==0){
			int w=p/3;
			q=g[0][0].cost%w;
			uf.Init(n*6);
			REP(i,n)REP(j,2)REP(k,3)for(auto e:g[i]){
				int c=e.cost/w;
				uf.Unite((i*2+j)*3+k,(e.to*2+(j^1))*3+(k+c*(j+1))%3);
			}
		}else{
			q=g[0][0].cost;
			uf.Init(n*2);
			REP(i,n)REP(k,2)for(auto e:g[i])
				uf.Unite(i*2+k,e.to*2+(k^1));
		}
		int tmp;
		gcd_pq=extgcd(q,p,inv_q,tmp);
		len=p/gcd_pq;
		assert(abs(inv_q)<len);
		if(inv_q<0)inv_q+=len;
		lg2.resize(len,-1);
		if(len==1){
			lg2[0]=0;
			ord=1;
		}else{
			int cur=1,i=0;
			do{
				lg2[cur]=i;
				cur=cur*2%len;
				i++;
			}while(cur!=1);
			ord=i;
		}
	}
	bool Query(int s,int t,int v){
		if(p==1)return true;
		if(p%3==0){
			int w=p/3;
			bool ans=false;
			REP(k,3){
				int v2=v-k*w;
				if(v2<0)v2+=p;
				if(v2%gcd_pq)
					continue;
				v2=(v2/gcd_pq*inv_q+1)%len;
				if(lg2[v2]==-1)
					continue;
				if(ord%2==0){
					ans|=uf.Same(s*6,(t*2+lg2[v2]%2)*3+k);
				}else{
					ans|=uf.Same(s*6,(t*2)*3+k)|uf.Same(s*6,(t*2+1)*3+k);
				}
			}
			return ans;
		}else{
			if(v%gcd_pq)
				return false;
			v=(v/gcd_pq*inv_q+1)%len;
			if(lg2[v]==-1)
				return false;
			bool ans=false;
			if(ord%2==0){
				ans=uf.Same(s*2,t*2+lg2[v]%2);
			}else{
				ans=uf.Same(s*2,t*2)|uf.Same(s*2,t*2+1);
			}
			return ans;
		}
	}
};

struct Solver2{
	int n;
	vector<vector<Edge>> g;
	int p;
	int ord,q;
	vi lg2;
	UnionFind uf;
	Solver2(const vector<vector<Edge>>&gg,const int pp):
	n(gg.size()),g(gg),p(pp){
		{
			int base=g[0][0].cost;
			REP(i,n)
				for(auto e:g[i])
					p=gcd(p,3*(e.cost-base)%p+p);
			REP(i,n)
				for(auto&e:g[i])
					e.cost%=p;
		}
		if(p==1)return;
		if(p%3==0){
			int w=p/3;
			q=g[0][0].cost%w;
			uf.Init(n*6);
			REP(i,n)REP(j,2)REP(k,3)for(auto e:g[i]){
				int c=e.cost/w;
				uf.Unite((i*2+j)*3+k,(e.to*2+(j^1))*3+(k*2+c)%3);
			}
		}else{
			q=g[0][0].cost;
			uf.Init(n*2);
			REP(i,n)REP(k,2)for(auto e:g[i])
				uf.Unite(i*2+k,e.to*2+(k^1));
		}
		lg2.resize(p,-1);
		if(q==0){
			lg2[0]=0;
			ord=1;
		}else{
			int cur=q,i=0;
			do{
				lg2[cur]=i;
				cur=cur*2%p;
				i++;
			}while(cur!=q);
			ord=i;
		}
	}
	bool Query(int s,int t,int v){
		if(p==1)return true;
		if(p%3==0){
			int w=p/3;
			bool ans=false;
			REP(k,3){
				int v2=(v-k*w+q)%p;
				if(v2<0)v2+=p;
				if(lg2[v2]==-1)
					continue;
				if(ord%2==0){
					ans|=uf.Same((s*2+lg2[v2]%2)*3+k,t*6);
				}else{
					ans|=uf.Same((s*2)*3+k,t*6)|uf.Same((s*2+1)*3+k,t*6);
				}
			}
			return ans;
		}else{
			v=(v+q)%p;
			if(lg2[v]==-1)
				return false;
			bool ans=false;
			if(ord%2==0){
				ans=uf.Same(s*2+lg2[v]%2,t*2);
			}else{
				ans=uf.Same(s*2,t*2)|uf.Same(s*2+1,t*2);
			}
			return ans;
		}
	}
};

signed main(){
	int n=read(),m=read(),q=read(),p=read();
	vector<vector<Edge>> g(n);
	REP(i,m){
		int a=read()-1,b=read()-1,c=read();
		g[a].PB(Edge{b,c});
		g[b].PB(Edge{a,c});
	}
	Solver2 sol(g,p);
	REP(i,q){
		int s=read()-1,t=read()-1,r=read()%p;
		bool ans=sol.Query(s,t,r);
		if(ans)Yes(0);
		else No(0);
	}
}