After being bored for too long, Wesley has decided to set another geometry problem!

This time, however, it is solvable by people that do not have a ~543~-line polygon template.

Wesley will ask you ~Q~ queries of ~6~ different types for ~N~ polygons:

• set square i: Set the ~i^\text{th}~ element to a square.

• set circle i: Set the ~i^\text{th}~ element to a circle.

• set triangle i: Set the ~i^\text{th}~ element to a triangle.

• get square i: Output 1 if the ~i^\text{th}~ element is a square or a 0, otherwise.

• get circle i: Output 1 if the ~i^\text{th}~ element is a circle or a 0, otherwise.

• get triangle i: Output 1 if the ~i^\text{th}~ element is a triangle or a 0, otherwise.

Initially, all ~N~ polygons are rhombuses and return 0 for all get queries.

Can you solve Wesley's obsession with geometry?

Constraints

~1 \le N, Q \le 10^5~

~1 \le i \le N~

Subtask 1 [20%]

~N = 1~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain ~N~ and ~Q~, the number of polygons and queries, respectively.

The next ~Q~ lines will contain one of the ~6~ queries above.

Output Specification

For each get query, output 1 if the polygons are the same; otherwise, output 0.

Sample Input 1

1 5
get square 1
set square 1
get square 1
set circle 1
get triangle 1

Sample Output 1

0
1
0

Sample Input 2

3 6
set square 2
set triangle 1
get square 2
set circle 3
get circle 3
get triangle 1

Sample Output 2

1
1
1