背景

SBW来到XY国，就立即被抓去管理交通

描述

XY国有(N+N)个城市，排成两行N列，从左至右从上到下一次编号为1,2,3,...,(2N-1),(2N)
每行相邻两个城市有道路相连
每列两个城市有道路相连
“这样城市与道路看起来像一行作文纸”，XY国国王XWQ认为这很不好
于是
左上角城市与右下角城市有道路相连
左下角城市与右上角城市有道路相连
“看起来像莫比乌斯环”，SBW评价道
XWQ有时会关闭一些道路以便他和LYH玩耍
当然为了交通也会开启一些
XWQ有时想知道某两个城市是否连通
SBW的任务就是告诉XWQ这两个城市是否连通

输入

第一行两个数N,M
接下来(N+N+N)行描述初始道路情况，每行3个数a,b,c，c==1表示a,b之间的道路开着，c==0表示关着
接下来M行，每行一个字符串str和两个数x,y
str=="Open" 表示开启a,b之间的道路
str=="Close" 表示关闭a,b之间的道路
str=="Ask" 表示询问x,y是否连通

输出

对每个询问输出1表示连通，或0表示不连通

样例

输入

3 10
1 2 0
2 3 1
3 4 0
4 5 1
5 6 0
6 1 1
1 4 1
2 5 0
3 6 0
Open 3 6
Ask 2 5
Ask 1 6
Ask 4 3
Close 1 6
Close 4 5
Open 5 6
Ask 2 5
Ask 1 6
Ask 1 3

输出

1
1
1
1
0
0

范围

40% N,M<=10
60% N,M<=1000
100% N,M<=\(10^5\) 1<=a,b,x,y<=(N+N) 0<=c<=1

限制

3000ms
512M