缓存（cache）

题目描述

Y 同学维护一个容量为 $k$ 的缓存。缓存中的每个编号互不相同，并且每个编号可能处于锁定或未锁定状态。初始缓存为空，所有新加入的编号均为未锁定状态。

接下来有 $q$ 个操作：

• A x：访问编号 $x$。若 $x$ 已在缓存中，输出 HIT，并把它视为最近访问过；若 $x$ 不在缓存中且缓存未满，加入 $x$ 并输出 MISS；若 $x$ 不在缓存中且缓存已满，则移除最久未访问的未锁定编号后加入 $x$ 并输出 MISS。如果缓存已满且所有编号都被锁定，则无法加入 $x$，输出 FAIL。
• P x：若 $x$ 在缓存中，则锁定 $x$。
• U x：若 $x$ 在缓存中，则解除 $x$ 的锁定。

请你按顺序输出所有 A 操作的结果。

输入格式

第一行包含两个整数 $k,q$。

接下来 $q$ 行，每行包含一个操作，格式如题目描述所示。

输出格式

对于每个 A 操作，输出一行 HIT、MISS 或 FAIL。

样例

样例输入 #1

2 7
A 1
A 2
P 1
A 3
U 1
A 3
A 4

样例输出 #1

MISS
MISS
MISS
HIT
MISS

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le k,q \le 2\times 10^5$，$1 \le x \le 10^9$。

• 特殊性质 A：保证没有 P 和 U 操作。
• 特殊性质 B：保证 $k \le 20$。