Relay Race Participation Query

You are given \(n\) runners numbered from \(1\) to \(n\). Initially, all runners are not participating in a relay race. You will receive \(m\) operations, each of which is one of the following three types:

• Type 1: 1 p — Mark runner \(p\) and all runners with indices \(\ge p\) as participating.
• Type 2: 2 p — Mark runner \(p\) and all runners with indices \(\le p\) as not participating.
• Type 3: 3 p — Query the participation status of runner \(p\). Print \(1\) if participating and \(0\) otherwise.

The operations are applied in the given order. Your task is to simulate the operations and answer all the queries (type 3 operations).

inputFormat

The first line contains two integers \(n\) and \(m\), where \(n\) is the number of runners and \(m\) is the number of operations.

Each of the next \(m\) lines contains two integers: the operation type \(c_i\) and an integer \(p_i\) (runner index).

All input is read from standard input (stdin).

outputFormat

For each type 3 operation, output a single line containing \(1\) if the queried runner is participating, or \(0\) otherwise. Output all answers to standard output (stdout) in the order of the queries.

## sample

6 8
1 3
3 2
3 4
1 1
2 5
3 6
2 1
3 1

0
1
1
0

</p>