When rain, nocLyt discovered a magical phenomenon that the rainwater always flow to the low-lying place.

Now, there is a N * N grid matrix (four Unicom) and above the first row was constantly raining. I have to tell you some rules:

1. Each grid is solid (represented as black) initially, the rain cannot flow into the solid grid.

2. You can "Open" a grid, if you "Open" that grid, that grid will becomes hollow (represented as white).

3. Rainwater can flow from top to bottom and from left to right (also right to left), but the precondition is that they are both hollow grid. (grid fill with rainwater represented as blue)

You can get more information from below picture.

Figure: from left to right are executed 50 times, 100 times, 150 times, 204 times "Open" operation.

We have three operation:

1. O i j: "Open" the grid (i, j).

2. F i j: You should tell me whether the grid(i, j) filled with rainwater. If yes, you should output 1, otherwise output 0.

4. C: You should tell me whether the rainwater has flow to the last row. If yes, you should output 1, otherwise output 0.

Note: The grid matrix from top to bottom number 1 to N, from left to right number 1 to N.

There are multiple test cases, each test case contains two positive integers N (1 <= N <= 5000) and M (1 <= M <= 1000000).
Following M lines, each line contain one of the three operation:
1. O i j (1 <= i, j <= N)
2. F i j (1 <= i, j <= N)
3. C

Output the answer.