捷克技术大学校园由 $$$n$$$ 建筑物组成,索引从 $$$1$$$ 到 $$$n$$$。在每栋建筑中,可以安排数学课,或计算机科学课,或两者都不安排(但不能两者都安排)。另外,每栋楼里最多有一名教授,每个教授要么是数学专家,要么是计算机科学专家。
作为 University Express Inc. 的实习生,您的工作是快速将教授运送到他们的班级。为此,您获得了一辆全新的两人踏板车,能够容纳您自己以及最多一名乘客。
最初,您是踏板车上唯一的人。当您到达某栋大楼时,您可以在该大楼接送教授。不过,为了提高您的任务效率,您最多可以开车前往每个 $$$n$$$ 建筑物一次,按照您选择的顺序(您也可以决定从哪里开始行程)。
您的行程结束后,在每个安排数学课的大楼中,必须有一名数学专家教授,在每个安排计算机科学课的大楼中,必须有一名计算机科学专家教授。
设计一个可以教授所有课程的行程。
输入
第一行包含一个整数 $$$n$$$ ($$$1\le n \le 2000$$$) — 校园内的建筑物数量。
第二行包含一个 $$$c$$$ 长度为 $$$n$$$ 的字符串,由字符 $$$\texttt{-}$$$、$$$\texttt{C}$$$、$$$\texttt{M}$$$ 组成 — 第 $$$i$$$ 个字符表示第 $$$i$$$ 栋大楼中安排的课程的主题。 $$$\texttt{C}$$$ 代表计算机科学,$$$\texttt{M}$$$ 代表数学,而 $$$\texttt{-}$$$ 表示第 $$$i$$$ 号楼没有课程。
第三行包含长度为 $$$n$$$ 的字符串 $$$p$$$,由字符 $$$\texttt{-}$$$、$$$\texttt{C}$$$、$$$\texttt{M}$$$ 组成 — 第 $$$i$$$ 个字符表示第 $$$i$$$ 栋大楼中教授的专业知识(如果有教授)。 $$$\texttt{C}$$$ 代表计算机科学,$$$\texttt{M}$$$ 代表数学,而 $$$\texttt{-}$$$ 表示第 $$$i$$$ 号楼没有教授。
可以保证,对于您的计划进行的所有测试,都存在有效的行程。
输出
在第一行打印一个整数 $$$l$$$ — 您选择的行程中的操作数量。
接下来的 $$$l$$$ 行的第 $$$i$$$ ($$$1 \leq i \leq l$$$) 必须包含以下三个命令之一:
1. $$$\texttt{DRIVE } x$$$ — 前往编号为 $$$x$$$ 的建筑物 ($$$1 \leq x \leq n$$$);
2. $$$\texttt{PICKUP}$$$ — 接最初在当前大楼的教授;
3. $$$\texttt{DROPOFF}$$$ — 将乘客教授送至当前大楼。
为了使行程有效,必须满足以下条件:
1. 两条 $$$\texttt{DRIVE}$$$ 指令不应前往同一栋大楼;
2. 每座特定建筑物最多依此顺序发出 1 条 $$$\texttt{DROPOFF}$$$ 及 1 条 $$$\texttt{PICKUP}$$$ 指令;
3. 对于所有 $$$\texttt{PICKUP}$$$ 指令,大楼内必须有一名教授,并且没有人已经骑过滑板车;
4. 对于所有$$$\texttt{DROPOFF}$$$指令,指令发出时必须有一名教授陪同;
5. 行程结束后,在每栋楼中,如果该楼有班级,则必须有该班级学科的教授专家(或者是最初,或者因为他们被送到那里)。
请特别注意,您无法接您刚刚送走的教授以使行程有效。
示例
输入 #1
3 CM- -CM
输出 #1
7 DRIVE 3 PICKUP DRIVE 2 DROPOFF PICKUP DRIVE 1 DROPOFF
输入 #2
1 C C
输出 #2
0
输入 #3
2 -M MC
输出 #3
4 DRIVE 1 PICKUP DRIVE 2 DROPOFF
注意
在第一个示例中,您首先开车前往编号为 $$$3$$$ 的大楼。然后你去接数学教授。将他送到正在上数学课的 $$$2$$$ 号楼后,您从那里接计算机科学教授,然后将她送到 $$$1$$$ 号楼,完成您的行程。