暂无测试数据。

Background

Special for beginners, ^_^

Description

对于一个空数列\(A\)，其最大长度为\(N\)，对于该数列，有如下操作：

1. push x 表示在\(A\)的末尾添加一个数x。若\(A\)之中已经有\(N\)个数，则将第一个数推出。
2. sort t 表示将\(A_1-A_{t-1}\)升序排序，将\(A_{t+1}-A_N\)降序排序。
3. know x 表示询问数字\(x\)第一次出现的位置。

现有\(Q\)次操作，对于每一次操作3，输出答案，下标从\(1\)开始。

Format

Input

输入文件名为array.in

第一行两个数\(N\)和\(Q\)。

其后\(Q\)行，每行一个字符串\(op\)和一个数字\(x\)或\(t\)。

Output

输出文件名为array.out

对于每一次操作\(3\)，输出答案。

Sample 1

Input

3 7
push 2
push 3
push 4
push 3
push 4
sort 3
know 3

Output

2

Limitation

对于\(100\%\)的数据：\(1\leq N\leq 2\times 10^6,1\leq Q\leq 5\times 10^5,op=\{"push","sort","know"\},1\leq t\leq A.size(),1\leq x\leq 2\times 10^9\)

Hint

对于\(Sample \ 1\)：

\(1. A=\{2\}\)
\(2. A=\{2,3\}\)
\(3. A=\{2,3,4\}\)
\(4. A=\{2,3,4,3\}\)
\(5. A=\{2,3,4,3,4\}\)
\(6. A=\{2,3,4,4,3\}\)