说明

时间限制：1 Sec 内存限制：512 MB 输入文件：seq.in 输出文件：seq.out

存在一个长度为 $ N $ 的数列 $ x = (x_0, x_1, x_2, \dots, x_{N-1}) $。

初始时，数列为 $ x = (0, 0, 0, \dots, 0) $。

给定 $ Q $ 个以下两种类型的查询，请按顺序处理：

查询类型

1. 区间更新

   ! L R K：对满足 $ L \le i \lt R $ 的所有 $ i $，将 $ x_i $ 更新为 $ x_i + K $。

2. 询问

   ?：找出数列 $ x $ 的当前状态首次出现的查询序号。

   - 初始状态（所有元素为 $0$）视为第 $0$ 次查询后的状态。

   - 假设当前询问查询为第 $ q $ 次查询（$ 1 \le q \le Q $），设第 $ i $ 次查询处理后的数列为 $ x^i $（初始状态为 $ x^0 $），需输出最小的 $ i $（$ 0 \le i \le q-1 $），使得 $ x^i = x^{q-1} $。

输入格式

第 $1$ 行：整数 $ N $ 和 $ Q $。

第 $ i+1 $ 行（$ 1 \le i \le Q $）：查询内容，格式为上述两种类型之一。

输出格式

对于每个询问查询，输出满足条件的最小 $ i $，每个结果占一行。

样例

样例 1

3 6
! 1 3 1
! 0 2 2
! 0 3 -2
?
! 2 3 2
?

3
1

样例说明：

处理过程如下：

- 初始时，数列 $ x = (0, 0, 0) $。

- 处理第 $1$ 个查询，结果为 $ x = (0, 1, 1) $。

- 处理第 $2$ 个查询，结果为 $ x = (2, 3, 1) $。

- 处理第 $3$ 个查询，结果为 $ x = (0, 1, -1) $。

- 回答第 $4$ 个查询：此时 $ x = (0, 1, -1) $，该值首次出现在第 $3$ 个查询处理后，因此输出 $3$。

- 处理第 $5$ 个查询，结果为 $ x = (0, 1, 1) $。

- 回答第 $6$ 个查询：此时 $ x = (0, 1, 1) $，该值曾出现在第 $1$ 个查询处理后和第 $5$ 个查询处理后，其中最早的查询编号为 $1$，因此输出 $1$。

样例 2

3 2
?
?

0
0

样例 3

100000 6
! 0 100000 1
! 0 100000 2
! 0 100000 3
! 0 100000 4
! 0 100000 -7
?

2

数据范围

对于 4% 的数据，$ Q = 1 $。

另有 4% 的数据，$ N = 1 $。

对于 20% 的数据，$ N \le 100 $，$ Q \le 10000 $。

对于 40% 的数据，$ N \le 10000 $，$ Q \le 50000 $。

对于 100% 的数据，$ 1 \le N \le 10^6 $，$ 1 \le Q \le 10^5 $。

对于区间更新的操作，参数满足 $ 0 \le L_i \lt N $，$ L_i \lt R_i \le N $，$ -100 \lt K_i \le 100 $，均为整数。