这是一道交互题。
在本题中，你必须实现一个简易的内存管理器，它可以分配和释放内存块。内存被表示为一个由 $n$ 个单元组成的数组 $M[1..n]$。大小为 $s$ 的内存块由 $s$ 个连续的内存单元组成。不同的内存块不允许共享同一个内存单元。
你的内存管理器必须能够分配大小为 1、2 和 3 的内存块，释放之前分配的内存块，并且可以移动之前分配的内存块。
有两种类型的请求：分配内存块和释放内存块。所有请求从 1 开始依次编号。
在分配新内存块之前以及释放内存块之后，你最多允许对当前已分配的内存块进行 2 次移动操作。
分配请求由集合 $\{1, 2, 3\}$ 中的一个整数指定，表示要分配的内存块的大小。
释放请求由一个负整数指定。整数 $-k$ 表示必须释放第 $k$ 次请求时分配的内存块。
你的内存管理器可以执行以下三种类型的操作：
- 分配："
A x" 分配请求的内存块，起始单元编号为 $x$。 - 移动："
M x y" 将起始位置为 $x$ 的内存块移动到起始位置为 $y$。 - 完成："
D" 报告在执行释放请求后的内存块移动已完成。
你必须实现一个内存管理器来执行所有操作，保证在任何时刻，已分配内存块的总大小最多为 $n - 1$。
交互格式
首先，你的程序必须读取一个整数 $n$ —— 内存数组的大小（$4 \le n \le 100\,000$）。之后会有一个或多个请求。
每个请求由一个整数指定。从 1 到 3 的正整数指定分配请求，负整数指定释放请求。0 表示输入结束，不需要进行处理，在读取到 0 后，你的程序必须退出。
在读取到分配请求后，你的程序可以执行最多 2 次移动操作，随后执行分配操作。
在读取到释放请求后，你的程序必须立即释放对应内存块所占用的单元（不需要对此释放操作进行报告），然后可以执行最多 2 次移动操作，最后执行完成操作。
所有执行的操作必须是合法的。
对于每次分配，当分配大小为 $s$ 的内存块时，其参数 $x$ 必须是某个单元的索引，且单元 $x, \dots, x + s - 1$ 必须是空闲的。
对于每次移动，其第一个参数 $x$ 必须是某个当前已分配内存块的起始单元。如果该内存块的大小为 $s$，则第二个参数 $y$ 必须是某个单元的索引，且单元 $y, \dots, y + s - 1$ 必须是空闲的。特别地，被移动内存块的源位置和目标位置不能共享任何公共单元。
所有请求都是合法的：没有内存块会被释放超过一次，在任何时刻所有已分配内存块的总大小最多为 $n - 1$，每个释放请求都对应某个分配请求的编号。
保证存在一种策略可以正确满足所有请求。
请求的数量最多为 $30\,000$。
样例
输入样例 1
7 3 2 -1 1 3 0
输出样例 1
A 1 A 4 D A 1 M 1 6 A 1