Dynamic Wall Building and Range Query

Walls are built dynamically on one-dimensional positions indexed 0 to n−1. Initially there are no walls. build i builds a wall at position i, and building there again does not change the state; query l r asks whether the closed interval [l,r] contains at least one wall. This site's input convention: the first line is n q, followed by q lines, each a build i or a query l r. This site's supplementary ranges: 1≤n,q≤200000, all indices lie in 0..n−1, and queries satisfy l≤r.

输入格式

The first line contains n q; then q lines of operations, build i or query l r.

输出格式

Output 0 or 1 for each query in order, separated by spaces; 1 if the interval contains a wall, otherwise 0.

样例 1

输入：

5 1
query 0 4

输出：

0

样例 2

输入：

5 3
build 2
query 0 4
query 3 4

输出：

1 0

样例 3

输入：

3 4
build 0
build 0
query 0 0
query 1 2

输出：

1 0