The kingdom of Tripbansai has an unusual traffic system. The city locations in the kingdom can be described as a grid and all the roads connect neighboring cities. This rectangular grid has 2 rows and C columns where every point represents a city. So there are 2 C cities and 3 C - 2 roads in this system.
Sometimes two adjacent cities become disconnected because of traffic jam, and sometimes the traffic problem has been solved so that a road can be usedd again. We can assume that every road is closed at first.
Ministry of Communications will give some instructions to you. Your task is to implement a program as a traffic response information system.
Each instruction appears as a single line in one ofthe formats below:
Close r1 c1 r2 c2 Close the road connecting the adjacent cities located on (r1, c1) and (r2, c2) .
Open r1 c1 r2 c2 Open the road connecting the adjacent cities located on (r1, c1) and (r2, c2) .
Ask r1 c1 r2 c2 Reply with Y if there exists a way from the city on (r1, c1) to the city on (r2, c2) ;
reply with N if there doesn’t.
Exit No more requests are forthcoming. The problem should exit.
The first line ofthe input contains a single integer T (1$\le$T$\le$11) , representing the number of test cases that follow.
The first line of each test case consists of a single integer C (1$\le$C$\le$100000) , which is the number of columns.
There are some lines following, each for an instruction. Each test case ends with an instruction ``Exit”. There are no more than 100000 instructions in each test case. All the roads are closed initially, and each case is an independent problem.
For each instruction
Ask r1 c1 r2 c2, display a line containing
對於一個 2 x C 的方格點來說，將會有
3 * C - 2 條邊。
- c 左上右上
- c 左上右下
- c 左下右上
- c 左下右下
- c 左上左下
- c 右上右下
r = 1 下方
r = 2 左方
c = left 右方
c = right
[l, r] 我們只維護這個區間的資訊，不考慮繞此外的結果。
而對於區間的編號，由左而右，構成 0, 1, 2, 3, …, C，每一個可以看作是一個方格。