该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

登录日志

时间限制：$1$ 秒。内存限制：$512$ MB。

题目描述

有 $n$ 条按时间顺序排列的日志，每条日志记录一个账号登录或退出。登录后，该账号变为在线；退出后，该账号变为离线。对已经在线的账号执行登录，或对已经离线的账号执行退出，账号状态均不变。

给定 $q$ 个相互独立的询问，每个询问包含两个下标 $l,r$。每次均从所有账号离线的状态开始，依次执行第 $l$ 条至第 $r$ 条日志。执行前以及每条日志执行后共 $r-l+2$ 个状态，求这些状态中同时在线的账号数的最大值。

输入格式

输入文件：login.in。

第一行包含两个整数 $n,q$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $t_i,b_i$，表示第 $i$ 条日志的类型和账号编号。$t_i=1$ 表示登录，$t_i=2$ 表示退出。

接下来 $q$ 行，每行包含两个整数 $l,r$，表示一个询问。

输出格式

输出文件：login.out。

对每个询问，输出一行一个整数，表示执行这段日志时同时在线的账号数的最大值。

样例

输入：

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

输出：

2
2
1
0

样例解释

第一个询问中，重复登录账号 $1$ 不会增加在线人数，第二次退出账号 $1$ 也没有影响，最多有两个账号同时在线。第二个询问从账号均离线开始，执行第 $3$ 条日志时账号 $1$ 上线，最多有两个账号同时在线。后两个答案分别为 $1,0$。

附加样例 $\texttt{login2.in/.ans}$、$\texttt{login3.in/.ans}$、$\texttt{login4.in/.ans}$ 分别满足测试点 $7\sim9$、$10\sim12$、$16\sim20$ 的限制。

数据范围

对于所有测试点，$1\le n,q\le3\times10^5$，$1\le t_i\le2$，$1\le b_i\le n$，$1\le l\le r\le n$。所有输入数值均为整数。

特殊性质 $A$：所有日志均为登录。

特殊性质 $B$：所有询问均满足 $l=1$。