邻居查询

难度：T2

【知识点：链表】【知识点：模拟】

前置知识：数组、循环、对应单链/双链/循环链的连接规则。

题目描述

编号 $1$ 到 $n$ 的人依次排队。指令 D x 删除 $x$，指令 Q x 查询 $x$ 当前的左右邻居编号。每次操作保证 $x$ 仍在队列中。某侧没有邻居时输出 $0$。至少有一次查询。

输入格式

首行 $n,m$；随后 $m$ 行各一条指令。

输出格式

每次查询输出一行两个整数，左邻居在前，用空格隔开。

样例输入

4 4
Q 2
D 2
Q 3
Q 1

样例输出

1 3
1 4
0 3

样例说明

删除 $2$ 后，$3$ 的左邻居变成 $1$。

数据范围

$1\le n\le2000$，$1\le m\le4000$，$1\le x\le n$。