M 镇的集市是一个受欢迎的旅游景点，但由于其独特的交通政策，没有车很难到达那里。交通部门决定将所有电车和公共汽车从市中心移走，因为它们阻碍了汽车通行。但汽车需要停车位，而市中心并没有多少停车位。因此，集市周围的小街道被改造成了非常长的平行停车位。年轻的 Johnny 虽然还没有车，但他已经在积极支持这项计划，因为他得到了一份新工作，负责管理其中一个新停车场。不幸的是，他不太擅长这份新工作，所以他肯定需要你的帮助。

Johnny 被分配到的街道长度为 $d$。他的工作是告诉即将到来的司机他们应该把车停在哪里，或者通知他们车太长停不下。形式上，他需要处理两种事件： 一辆长度为 $l_i$、车牌号为 $p_i$ 的汽车驶来； 车牌号为 $p_i$ 的汽车离开。

当一辆车驶来时，Johnny 必须找到能容纳该车的、最短的可用连续空位。如果有多个这样的位置，他应该选择最靠近集市的那一个（即从停车场起点看最早的位置）。汽车司机是平行停车的大师，他们的车辆非常灵活，总是停在 Johnny 找到的空间的最前端；以至于他们可以紧贴前车，在极端情况下，他们甚至可以同时紧贴前车和后车。这种紧凑的停车方式即使在离开停车场时也不会造成问题。

输入格式

输入的第一行包含两个整数 $d$ 和 $q$，用空格分隔，分别表示停车场的长度和事件的数量（$1 \le d \le 10^9$，$1 \le q \le 10^6$）。

接下来的 $q$ 行，每行以一个字母 P 或 O 开头，表示事件的类型（分别为汽车驶来和汽车离开），后跟一个空格和一个车牌号 $p_i$。车牌号是一个非空字符串，最多包含 10 个字符，每个字符要么是小写拉丁字母（a-z），要么是数字（0-9）。

如果该行描述的是汽车驶来，那么它在车牌号后还会包含一个空格，以及该车的（整数）长度 $l_i$（$1 \le l_i \le 10^9$）。

每辆车最多尝试寻找一次停车位：游客从不访问集市超过一次，如果他们找不到停车位，这一点就更是如此。

如果该行描述的是汽车离开，则不再包含其他内容。但是，保证车牌号 $p_i$ 对应于一辆已经尝试过寻找停车位的汽车。注意，该车不一定找到了停车位，即使在这种情况下，它也不必立即离开（即其他车辆可能在它之前离开），甚至可能根本不离开。

输出格式

输出应包含恰好 $q$ 行，每行描述输入中下一个事件的结果。

描述汽车驶来的事件的结果是一个整数 $o_i$ —— 该车应停放的位置（从停车场起点开始计算），如果无法停放该车，则输出单词 NIE。

描述汽车离开的事件的结果是单词 OK（如果该车确实停放了且现在正在离开），否则输出单词 BRAK。

样例

输入 1

10 7
P dw12345 1
P dwr12345 2
P we11111 8
O dw12345
P d0icpc 3
P dw000xx 1
O we11111

输出 1

0
1
NIE
OK
3
0
BRAK

说明

每次操作后停车场的状态如下图所示：

汽车 dw12345 和 dwr12345 先后停在位置 0 和 1。汽车 we11111 太长，无法停放。在 dw12345 离开后，d0icpc 停在 dwr12345 后面，位置为 3，然后 dw000xx 停在 dw12345 腾出的位置 0。由于 we11111 没有找到停车位，其离开操作的答案为 BRAK。