在二维平面上有两条水平直线 $y = 0$ 和 $y = H$。在这两条线之间最初有 $n$ 个微小的木板，可以看作是点。第 $i$ 个木板位于 $(x_i, y_i)$。

维护以下三种类型的 $q$ 次操作：

• $+ x y$：在平面上添加一个位于 $(x, y)$ 的木板。
• $- x y$：从平面上移除位于 $(x, y)$ 的木板。
• $? x y v_y g$：从 $(x, y)$ 释放一个弹球。 设 $\vec{v} = (v_x, v_y)$ 为球的速度（即如果球当前位于 $(x, y)$，经过 $\epsilon$ 时间后它将移动到 $(x + v_x\epsilon, y + v_y\epsilon)$）。如果 $g \ge x$，则 $v_x = 1$，否则 $v_x = -1$，而 $v_y$ 由查询给出。$v_y$ 的值为 $1$ 或 $-1$。 当球撞击木板或两条水平直线之一时，$v_y$ 会反转（即 $v_y$ 变为 $-v_y$），而 $v_x$ 保持不变。 计算当弹球的 $x$ 坐标等于 $g$ 时，其 $y$ 坐标的值。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $H, n$ 和 $q$ ($2 \le H \le 10^9, 1 \le n, q \le 10^5$)，分别表示上方水平直线的位置、初始木板数量和操作次数。

接下来的 $n$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i \le 10^9, 1 \le y_i < H$)，表示第 $i$ 个木板的位置。

接下来的 $q$ 行，第 $i$ 行首先包含一个字符 $op$ ($op \in \{+, -, ?\}$)，表示第 $i$ 次操作的类型。

• 如果 $op = +$，则随后有两个整数 $x$ 和 $y$ ($1 \le x \le 10^9, 1 \le y < H$)，表示要添加的木板位置。保证当前 $(x, y)$ 处没有木板。
• 如果 $op = -$，则随后有两个整数 $x$ 和 $y$ ($1 \le x \le 10^9, 1 \le y < H$)，表示要移除的木板位置。保证当前 $(x, y)$ 处存在木板。
• 如果 $op = ?$，则随后有四个整数 $x, y, v_y$ 和 $g$ ($1 \le x, g \le 10^9, 1 \le y < H, v_y \in \{-1, 1\}$)，表示弹球的初始位置、初始 $y$ 轴速度和目标 $x$ 坐标。保证当前 $(x, y)$ 处没有木板。

保证所有测试数据的 $n$ 之和与 $q$ 之和均不超过 $2 \times 10^5$。

输出格式

对于每组第三类操作，输出一行，包含一个整数，表示答案。

样例

样例输入 1

2
5 2 8
4 2
6 4
? 10 4 -1 3
+ 8 2
? 3 3 -1 12
? 3 1 1 12
- 4 2
? 3 3 -1 12
? 3 1 1 12
? 7 3 1 6
10 1 2
5 5
? 9 2 1 9
? 9 2 -1 9

样例输出 1

1
4
2
2
4
4
2
2

说明

我们用下图说明第一个样例测试中的查询。木板用菱形表示。