To seem more cultured, Max has undertaken consuming all the best media generated ever!

Currently, he has ~N~ different lists of media that he needs to fill up, but he cannot remember if he already added some media, so he will ask you ~Q~ queries of ~2~ types:

1 i name: Output ~1~ if the ~i^\text{th}~ media list already has ~name~ in it and ~0~ otherwise.

2 i name: Insert ~name~ into the ~i^\text{th}~ media list.

Can you help maintain Max's media list?

Constraints

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

~1 \le i \le N~

Each ~name~ will be at most ~5~ lowercase letters.

Subtask 1 [40%]

~N = 1~

Subtask 2 [60%]

No additional constraints.

Note: Fast I/O might be required to fully solve this problem (e.g., BufferedReader for Java).

Input Specification

The first line will contain two integers, ~N~ and ~Q~, the number of media lists and queries, respectively.

The next ~Q~ lines will contain one of the ~2~ types of queries listed above.

Output Specification

For each type ~1~ query, output ~1~ if that media list has ~name~ in it and ~0~ otherwise.

Sample Input 1

1 6
1 1 test
2 1 test
2 1 test
1 1 test
2 1 blah
1 1 pf

Sample Output 1

0
1
0

Sample Input 2

2 6
1 1 test
2 1 test
2 1 test
1 2 test
2 2 blah
1 2 blah

Sample Output 2

0
0
1