Altina 正在建立一个区间集合。一个区间定义为两个正整数 $[l, r]$，满足 $l < r$。我们称该区间的长度为 $r - l$。此外，如果 $l \le x$ 且 $y \le r$，则称区间 $[l, r]$ 包含另一个区间 $[x, y]$。特别地，每个区间都包含其自身。

对于一个非空的区间集合 $S$，我们定义公共区间集为所有被 $S$ 中每一个区间 $[l, r]$ 所包含的区间 $[x, y]$。如果公共区间集非空，则称 $S$ 的最大公共区间为长度最大的那个公共区间。

对于同一个集合 $S$，我们定义包含区间集为所有包含 $S$ 中每一个区间 $[l, r]$ 的区间 $[x, y]$。注意该集合总是非空的，因此我们称 $S$ 的最小包含区间为长度最小的那个包含区间。

起初，Altina 的集合中没有任何区间。共有 $Q$ 个事件会改变她拥有的区间集合。

第一类事件是 Altina 向她的集合中添加一个区间 $[l, r]$。注意，该区间可能与她集合中已有的另一个区间 $[l, r]$ 相同。它们应被视为独立的区间。

第二类事件是 Altina 从她的集合中移除一个现有的区间 $[l, r]$。注意，如果 Altina 有多个相同的 $[l, r]$ 区间，她只会移除其中一个。

在每次事件之后，Altina 会从她拥有的区间集合中选择一个非空子集 $S$，该子集需满足以下条件：

• 在所有 Altina 可以选择的集合 $S$ 中，如果可能，她会选择一个没有最大公共区间的集合。如果无法做到，则她会选择一个最大公共区间长度尽可能小的集合。
• 在所有满足上述条件的集合 $S$ 中，她会选择一个最小包含区间长度尽可能小的集合。

你的任务是确定在每次事件后，Altina 所选集合 $S$ 的最小包含区间的长度。

输入格式

第一行包含 $Q$ ($1 \le Q \le 500\,000$)，表示添加和移除操作的总数。接下来的 $Q$ 行，每行格式如下：

• A l r：向 Altina 的集合中添加区间 $[l, r]$。
• R l r：从 Altina 的集合中移除一个区间 $[l, r]$ 的实例。保证被移除的区间存在，且移除后集合非空。

对于所有子任务，$1 \le l < r \le 1\,000\,000$。

• 在 25 分的测试中，有 3 分满足 $Q \le 500$。
• 在 25 分的测试中，另有 8 分满足 $Q \le 12\,000$。
• 在 25 分的测试中，另有 7 分满足 $Q \le 50\,000$。
• 在 25 分的测试中，另有 4 分满足以下条件：在每次事件后，对于 Altina 集合中任意两个独立的区间 $[l_1, r_1]$ 和 $[l_2, r_2]$，都有 $r_1 < l_2$ 或 $r_2 < l_1$。

输出格式

输出包含 $Q$ 行，每行包含题目描述中 Altina 所选集合 $S$ 的最小包含区间的长度。

样例

样例输入 1

5
A 1 5
A 2 7
A 4 6
A 6 8
R 4 6

样例输出 1

4
6
5
4
7

说明

在添加区间 $[1, 5]$ 后，只有一个区间，因此 $S = \{[1, 5]\}$ 是唯一的有效选择，最小包含区间为 $[1, 5]$。

在添加区间 $[2, 7]$ 后，$S = \{[1, 5], [2, 7]\}$ 的最大公共区间为 $[2, 5]$，最小包含区间为 $[1, 7]$。

在添加区间 $[4, 6]$ 后，$S = \{[1, 5], [4, 6]\}$ 的最大公共区间为 $[4, 5]$，最小包含区间为 $[1, 6]$。

在添加区间 $[6, 8]$ 后，$S = \{[4, 6], [6, 8]\}$ 没有最大公共区间，其最小包含区间为 $[4, 8]$。注意 $S = \{[1, 5], [6, 8]\}$ 也没有最大公共区间，但其最小包含区间 $[1, 8]$ 的长度大于 $[4, 8]$。

在移除区间 $[4, 6]$ 后，$S = \{[1, 5], [6, 8]\}$ 没有最大公共区间，最小包含区间为 $[1, 8]$。