成功的女企业家 Elena Možus 的人生目标是用人工智能取代所有人类劳动力。为了加速这一进程，她得出结论：有必要参与克罗地亚的立法工作。她的计划传达到了国家总统那里，总统任命她为新成立的自动化逻辑原理与分析思维部（简称 MALNAR）的负责人。他们的第一个任务是自动化下面这款游戏。

游戏由两名玩家组成。每名玩家各自拥有一个大小为 $K$ 的集合，其中包含 $1$ 到 $N$ 之间的（互不相同的）数字。每名玩家只能看到自己集合中的数字，游戏的目标是求出这两个集合的交集大小。

玩家不能直接交流，只能通过一块公共棋盘来放置棋子。

游戏规则如下：

• 棋盘由 $N$ 个空格组成，可以在其上放置棋子。
• 玩家轮流在任意一个尚未被占用的格子上放置棋子。一旦某个格子被放置了棋子，该格子即被视为已占用，不能再放置其他棋子。
• 第一名玩家放置蓝色棋子，第二名玩家放置红色棋子。
• 两名玩家在任何时刻都可以看到棋盘的完整状态。
• 当轮到某名玩家行动时，他可以选择不放置棋子，而是直接结束游戏，并宣布两个给定集合的交集大小。若棋盘上已没有空格，玩家必须结束游戏。

在游戏过程中，玩家只能通过棋盘进行交流；当然，在游戏开始之前，他们可以事先商定好策略。

MALNAR 决定用一个具有绝对正确策略、并且在读取棋盘状态后可以立刻行动的人工智能自动化系统来替代玩家。请你帮助 MALNAR，为两名玩家设计策略，保证在某个时刻至少有一名玩家结束游戏并宣布正确的交集大小。

为了让自动化系统能够快速行动，策略将表现为：对每一种可能的棋盘状态，指定应当执行的动作。这意味着自动化系统无法得知导致当前状态的历史行动序列，而只能基于当前给定的棋盘状态来做出决策。

输入格式

第一行是一个自然数 $P$（$P = 1$ 或 $P = 2$），表示当前程序对应的是第一名玩家还是第二名玩家。

第二行包含自然数 $N$ 和 $K$，含义如题目描述。

第三行包含 $K$ 个互不相同的、介于 $1$ 到 $N$ 之间的自然数，表示给定的数字集合。

第四行是自然数 $T$，表示需要给出行动的棋盘状态数量。在测试数据中，$T$ 始终等于所有可能棋盘状态的总数，这意味着所选策略必须为每一种可能的棋盘状态指定一个动作。这里的“可能”是指该状态在游戏过程中可能出现。不过，仅在样例中，$T$ 可能取更小的值。

接下来的 $T$ 行中，每一行描述一种可能的棋盘状态。棋盘状态由 $N$ 个字符组成，字符可以是：

• P：蓝色棋子；
• C：红色棋子；
• .：空格。

输出格式

对于给定的每一个棋盘状态，输出一行，格式为 + m 或 ! m，其中 $m$ 为某个整数。

• 输出形式 + m 表示在棋盘的第 $m$ 个位置放置一个棋子。要使输出合法，必须满足 $1 \le m \le N$，且所选位置必须是空的。
• 输出形式 ! m 表示宣布给定集合的交集大小为 $m$，并结束游戏。要使输出合法，必须满足 $0 \le m \le N$。

子任务

评分将分两步进行。首先在 $P = 1$ 的测试数据上运行程序，然后在 $P = 2$ 的测试数据上再次运行。两次运行中，输入数据 $N$ 和 $K$ 的值相同。

在假设两次运行中程序输出均合法的前提下，评测程序将根据你输出的策略描述来模拟完整的游戏过程。如果模拟结果最终以正确的交集大小结束，则你的解法被认为是正确的。程序的运行时间为两次评测运行时间之和。

在所有子任务中，均满足：

• $2 \le N \le 16$
• $1 \le K \le N$

样例数据

样例输入 1

1
4 2
2 3
3
....
P.C.
PCCP

样例输出 1

+ 1
+ 4
! 1

样例输入 2

2
4 2
1 3
2
P...
P.CP

样例输出 2

+ 3
+ 2

样例说明

以上仅展示了一种可能的策略。下面给出对应的游戏过程：