2019.8.30

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%ulld",&x)
#define RDL2(x,y) scanf("%ulld %ulld",&x,&y)
#define RDL3(x,y,z) scanf("%ulld %ulld %ulld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxm (1111+10)
#define maxn (1000+5)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false);cin.tie(0)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,m,k,l;
int dp[maxn][400];
int aa[maxn],bb[maxn],cc[maxn];
int main()
{
	NEG(dp);
	acc;cin>>n>>m>>k>>l;int zero=200;
	for(int i=zero+k;i<=zero+100;i++)dp[n+1][i]=2;
	for(int i=zero+l+1;i<zero+k;i++)dp[n+1][i]=1;
	for(int i=zero-100;i<=zero+l;i++)dp[n+1][i]=0;
	for(int i=1;i<=n;i++)cin>>aa[i]>>bb[i]>>cc[i];
	int nxt;
	for(int i=n;i;i--)
	{
		int a,b,c;a=aa[i],b=bb[i],c=cc[i];
		if(i&1)for(int s=-100;s<=100;s++)
			{
				nxt=min(a+s,100);
				if(a&&dp[i+1][zero+nxt]==2){dp[i][zero+s]=2;continue;}
				nxt=max(-100,s-b);
				if(b&&dp[i+1][zero+nxt]==2){dp[i][zero+s]=2;continue;}
				nxt=-s;
				if(c&&dp[i+1][zero+nxt]==2){dp[i][zero+s]=2;continue;}
				nxt=min(a+s,100);
				if(a&&dp[i+1][zero+nxt]==1){dp[i][zero+s]=1;continue;}
				nxt=max(-100,s-b);
				if(b&&dp[i+1][zero+nxt]==1){dp[i][zero+s]=1;continue;}
				nxt=-s;
				if(c&&dp[i+1][zero+nxt]==1){dp[i][zero+s]=1;continue;}
				nxt=min(a+s,100);
				if(a&&dp[i+1][zero+nxt]==0){dp[i][zero+s]=0;continue;}
				nxt=max(-100,s-b);
				if(b&&dp[i+1][zero+nxt]==0){dp[i][zero+s]=0;continue;}
				nxt=-s;
				if(c&&dp[i+1][zero+nxt]==0){dp[i][zero+s]=0;continue;}
			}
		else for(int s=-100;s<=100;s++)
			{
				nxt=min(a+s,100);
				if(a&&dp[i+1][zero+nxt]==0){dp[i][zero+s]=0;continue;}
				nxt=max(-100,s-b);
				if(b&&dp[i+1][zero+nxt]==0){dp[i][zero+s]=0;continue;}
				nxt=-s;
				if(c&&dp[i+1][zero+nxt]==0){dp[i][zero+s]=0;continue;}
				nxt=min(a+s,100);
				if(a&&dp[i+1][zero+nxt]==1){dp[i][zero+s]=1;continue;}
				nxt=max(-100,s-b);
				if(b&&dp[i+1][zero+nxt]==1){dp[i][zero+s]=1;continue;}
				nxt=-s;
				if(c&&dp[i+1][zero+nxt]==1){dp[i][zero+s]=1;continue;}
				nxt=min(a+s,100);
				if(a&&dp[i+1][zero+nxt]==2){dp[i][zero+s]=2;continue;}
				nxt=max(-100,s-b);
				if(b&&dp[i+1][zero+nxt]==2){dp[i][zero+s]=2;continue;}
				nxt=-s;
				if(c&&dp[i+1][zero+nxt]==2){dp[i][zero+s]=2;continue;}
			}
		//for(int s=-100;s<=100;s++)see(i),see(s),see(dp[i][s+zero]),NL;
		
	}
		if(dp[1][m+zero]==2)cout<<"Good Ending";
		else if(dp[1][m+zero]==1)cout<<"Normal Ending";
		else cout<<"Bad Ending";
	return 0;
}

#include<bits/stdc++.h>
#define RD1(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d %d",&x,&y)
#define RD3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define RDL1(x) scanf("%ulld",&x)
#define RDL2(x,y) scanf("%ulld %ulld",&x,&y)
#define RDL3(x,y,z) scanf("%ulld %ulld %ulld",&x,&y,&z)
#define CLR(x) memset(x,0,sizeof(x))
#define NEG(x) memset(x,0xff,sizeof(x))
#define maxm (1111+10)
#define maxn (500*500*2+5)
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mod (1000000007)
#define pi acos(-1)
#define eps 1e-14
#define acc ios::sync_with_stdio(false);cin.tie(0)
#define inf 0x3f3f3f3f
#define INF(x) memset(x,inf,sizeof(x))
#define CLRQ(Q) while(!(Q).empty())(Q).pop()
#define see(x) (cerr<<(#x)<<'='<<(x)<<' ')
#define NL printf("\n")
#define fi freopen("C:\\Users\\Administrator\\Desktop\\in","r",stdin)
#define fo freopen("C:\\Users\\Administrator\\Desktop\\out","w",stdout)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n,m;
int head[maxn],to[maxn],pre[maxn],tot1,dep[maxn];
int f[maxn][30];
void adde(int u,int v)
{
	to[++tot1]=v,pre[tot1]=head[u],head[u]=tot1;
}
inline int tt(int x,int y)
{
	return (x-1)*m+y;
}
struct E
{
	int u,v,d;
}e[maxn];
bool operator<(E x,E y)
{
	return x.d>y.d;
}
struct DS
{
	int fa[maxn];
	void init(int n)
	{
		for(int i=1;i<=n;i++)fa[i]=i;
	}
	int getf(int x)
	{
		return x==fa[x]?x:fa[x]=getf(fa[x]);
	}
	bool merg(int x,int y)
	{
		int p1=getf(x),p2=getf(y);
		if(p1==p2)return 0;
		fa[p2]=p1;return 1;
	}
}ds;
void dfs(int u,int fa)
{
	f[u][0]=fa;for(int i=1;i<=25;i++)f[u][i]=f[f[u][i-1]][i-1];
	//see(u),see(fa),NL;
	for(int i=head[u];i;i=pre[i])
	{
		int v=to[i];//see(u),see(v),NL;
		if(v==fa)continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
    for(int i=25;i>=0;i--)if(dep[x]-(1<<i)>=dep[y])
        x=f[x][i];
    if(x==y)return x;
    for(int i=25;i>=0;i--)if(f[x][i]!=f[y][i])
        x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main()
{
	acc;cin>>n>>m;
	int tot=0;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		char c;int d;
		cin>>c>>d;if(c=='D')
		{
			int u=tt(i,j),v=tt(i+1,j);
			e[tot++]={u,v,d};
			//see(u),see(v),NL;
			//adde(tt(i,j),tt(i+1,j),d),adde(tt(i+1,j),tt(i,j),d);
		}
		cin>>c>>d;if(c=='R')
		{
			int u=tt(i,j),v=tt(i,j+1);
			e[tot++]={u,v,d};
			//see(u),see(v),NL;
			//adde(tt(i,j+1),tt(i,j),d),adde(tt(i,j),tt(i,j+1),d);
		}
	}
	sort(e,e+tot);
	//see(tot);
	ds.init(n*m);
	int cnt=0;
	for(int i=0;i<tot&&cnt<n*m-1;i++)
	{
		int u=e[i].u,v=e[i].v,d=e[i].d;
		if(ds.merg(u,v))
		{
			//see(u),see(v),NL;
			cnt++,adde(u,v),adde(v,u);
		}
	}
	//see(tot1),NL;
	dfs(1,0);
	int q;cin>>q;while(q--)
	{
		int x,y,xx,yy;cin>>x>>y>>xx>>yy;
		x=tt(x,y),y=tt(xx,yy);
		//see(x),see(y),NL;
		cout<<dep[x]+dep[y]-dep[lca(x,y)]*2<<endl;
	}
	return 0;
}