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