动态图的连通性当然是可以用LCT维护的。但这相当的不优美，毕竟这样做没有用到任何该图的性质，LCT自带的大常数也会使其跑得非常慢。
考虑用线段树维护区间左右端四个点之间各自的连通性（仅经过该区间内路径）。查询时考虑几种绕来绕去的情况。
剩下的是大讨论。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 100010
int n;
bool r[N][];
struct data{int L,R;bool f[],w[];//0 u 1 d 2 l 3 r 4 z 5 f
}tree[N<<];
int whichop(int x,int y,int u,int v)
{
if (y==v) return ;
if (x==u) return x;
return x==?:;
}
void build(int k,int l,int r)
{
tree[k].L=l,tree[k].R=r;
if (l==r) {tree[k].f[]=tree[k].f[]=;return;}
else tree[k].w[]=tree[k].w[]=;
int mid=l+r>>;
build(k<<,l,mid);
build(k<<|,mid+,r);
}
data merge(data x,data y)
{
data v;v.L=x.L,v.R=y.R;
v.w[]=x.w[]||y.w[]||!r[x.R][];
v.w[]=x.w[]||y.w[]||!r[x.R][];
v.f[]=x.f[]&&y.f[]&&r[x.R][]||x.f[]&&y.f[]&&r[x.R][];
v.f[]=x.f[]&&y.f[]&&r[x.R][]||x.f[]&&y.f[]&&r[x.R][];
v.f[]=x.f[]||x.f[]&&r[x.R][]&&r[x.R][]&&y.f[];
v.f[]=y.f[]||y.f[]&&r[x.R][]&&r[x.R][]&&x.f[];
v.f[]=x.f[]&&r[x.R][]&&y.f[]||x.f[]&&r[x.R][]&&y.f[];
v.f[]=x.f[]&&r[x.R][]&&y.f[]||x.f[]&&r[x.R][]&&y.f[];
return v;
}
void modifyrow(int k,int x)
{
if (tree[k].L==tree[k].R) return;
if (tree[k].L+==tree[k].R) {tree[k]=merge(tree[k<<],tree[k<<|]);return;}
int mid=tree[k].L+tree[k].R>>;
if (x<mid) modifyrow(k<<,x);
else if (x>mid) modifyrow(k<<|,x);
tree[k]=merge(tree[k<<],tree[k<<|]);
}
void modifyline(int k,int x,int op)
{
if (tree[k].L==tree[k].R)
{
tree[k].f[]=tree[k].f[]=;
tree[k].f[]=tree[k].f[]=tree[k].f[]=tree[k].f[]=op;
return;
}
int mid=tree[k].L+tree[k].R>>;
if (x<=mid) modifyline(k<<,x,op);
else modifyline(k<<|,x,op);
tree[k]=merge(tree[k<<],tree[k<<|]);
}
data query(int k,int l,int r)
{
if (tree[k].L==l&&tree[k].R==r) return tree[k];
int mid=tree[k].L+tree[k].R>>;
if (r<=mid) return query(k<<,l,r);
else if (l>mid) return query(k<<|,l,r);
else return merge(query(k<<,l,mid),query(k<<|,mid+,r));
}
bool isempty(int k,int L,int R,int x)
{
if (tree[k].L==L&&tree[k].R==R) return !tree[k].w[x];
int mid=tree[k].L+tree[k].R>>;
if (R<=mid) return isempty(k<<,L,R,x);
else if (L>mid) return isempty(k<<|,L,R,x);
else return r[tree[k<<].R][x]&&isempty(k<<,L,mid,x)&&isempty(k<<|,mid+,R,x);
}
int queryleft(int k,int p,int x)
{
if (tree[k].L==tree[k].R) return tree[k].L;
int mid=tree[k].L+tree[k].R>>;
if (p<=mid) return queryleft(k<<,p,x);
else return isempty(k<<|,tree[k<<|].L,p,x)&&r[tree[k<<].R][x]?queryleft(k<<,tree[k<<].R,x):queryleft(k<<|,p,x);
}
int queryright(int k,int p,int x)
{
if (tree[k].L==tree[k].R) return tree[k].L;
int mid=tree[k].L+tree[k].R>>;
if (p<=mid) return isempty(k<<,p,tree[k<<].R,x)&&r[tree[k<<].R][x]?queryright(k<<|,tree[k<<|].L,x):queryright(k<<,p,x);
else return queryright(k<<|,p,x);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj1018.in","r",stdin);
freopen("bzoj1018.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
build(,,n);
char c=getchar();while (c<'A'||c>'Z') c=getchar();
while (c!='E')
{
int x=read(),y=read(),u=read(),v=read();
if (y>v) swap(x,u),swap(y,v);x--,u--;
if (c=='O')
{
if (y==v) modifyline(,y,);
else r[y][x]=,modifyrow(,y);
}
else if (c=='C')
{
if (y==v) modifyline(,y,);
else r[y][x]=,modifyrow(,y);
}
else
{
y=queryleft(,y,x);
v=queryright(,v,u);
printf(query(,y,v).f[whichop(x,y,u,v)]?"Y\n":"N\n");
}
c=getchar();while (c<'A'||c>'Z') c=getchar();
}
return ;
}