311203: CF1949G. Scooter

G. Scootertime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

The Czech Technical University campus consists of $n$ buildings, indexed from $1$ to $n$. In each building, there can be a math class scheduled, or a computer science class, or neither (but not both). Additionally, in each building, there is at most one professor, and each professor is either an expert in mathematics or in computer science.

As an intern at University Express Inc., your job is to quickly transport the professors to their classes. For this, you have been granted a brand new two-person scooter, able to accommodate yourself, plus at most one passenger.

Initially, you are the only person on the scooter. When you arrive at a building, you may drop off or pick up professors to/from that building. However, in order to improve the efficiency of your task, you are allowed to drive to each of the $n$ buildings at most once, in the order of your choice (you can also decide where to start the itinerary).

After the end of your itinerary, in each building where a math class is scheduled, there must be a professor expert in math, and in each building where a computer science class is scheduled, there must be a professor expert in computer science.

Devise an itinerary that makes it possible to teach all classes.

Input

The first line contains an integer $n$ ($1\le n \le 2000$) — the number of buildings in the campus.

The second line contains a string of $c$ of length $n$ consisting of the characters $\texttt{-}$, $\texttt{C}$, $\texttt{M}$ — the $i$-th character denotes the subject of the class scheduled in the $i$-th building. $\texttt{C}$ stands for computer science, $\texttt{M}$ stands for mathematics, while $\texttt{-}$ means that there is no class scheduled in the $i$-th building.

The third line contains a string $p$ of length $n$ consisting of the characters $\texttt{-}$, $\texttt{C}$, $\texttt{M}$ — the $i$-th character denotes the expertise of the professor in the $i$-th building (if there is a professor). $\texttt{C}$ stands for computer science, $\texttt{M}$ stands for mathematics, while $\texttt{-}$ means that there is no professor in the $i$-th building.

It is guaranteed that, for all tests given to your program, there exists a valid itinerary.

Output

In the first line print an integer $l$ — the number of operations in your chosen itinerary.

The $i$-th ($1 \leq i \leq l$) of the next $l$ lines must contain one of three commands:

1. $\texttt{DRIVE } x$ — go to the building with the number $x$ ($1 \leq x \leq n$);
2. $\texttt{PICKUP}$ — pick up the professor which was initially at the current building;
3. $\texttt{DROPOFF}$ — drop off the passenger professor at the current building.

In order for the itinerary to be valid, the following conditions must hold:

1. No two $\texttt{DRIVE}$ instructions should go to the same building;
2. At most one $\texttt{DROPOFF}$ and one $\texttt{PICKUP}$ instruction in this order should be issued at each specific building;
3. For all $\texttt{PICKUP}$ instructions, there must be a professor initially at the building, as well as no one already riding along on the scooter;
4. For all $\texttt{DROPOFF}$ instructions, there must be a professor riding along at the time of the command;
5. After the itinerary, in each building, if there is a class in that building, there must be a professor expert in the class' subject (either initially, or because they were dropped off there).

Note that, in particular, you cannot pick up a professor that you just dropped off for an itinerary to be valid.

ExamplesInput

3
CM-
-CM

Output

7
DRIVE 3
PICKUP
DRIVE 2
DROPOFF
PICKUP
DRIVE 1
DROPOFF

Input

1
C
C

Output

0

Input

2
-M
MC

Output

4
DRIVE 1
PICKUP
DRIVE 2
DROPOFF

Note

In the first sample, You start by driving to building number $3$. You then pick up the mathematics professor. After dropping him off at building number $2$, where a mathematics class is being held, you pick up the computer science professor from there, and drop her off at building number $1$, finishing your itinerary.

题目大意：
这个题目是关于一个校园里有 n 栋楼的问题。每栋楼可能安排了数学课、计算机课，或者两者都没有。每栋楼最多有一个教授，教授可能是数学专家或计算机科学专家。你有一个两座的摩托车，可以带你和最多一个乘客。你需要设计一个行程，使得每个安排了课程的楼都有相应的专家教授上课。你可以在每个楼最多访问一次，并且可以自由选择访问的顺序。

输入输出数据格式：
输入：
- 第一行是一个整数 n (1 ≤ n ≤ 2000)，表示楼的数量。
- 第二行是一个长度为 n 的字符串，由字符 '-'、'C'、'M' 组成，第 i 个字符表示第 i 栋楼安排的课程的科目。'C' 表示计算机科学，'M' 表示数学，'-' 表示没有安排课程。
- 第三行也是一个长度为 n 的字符串，由字符 '-'、'C'、'M' 组成，第 i 个字符表示第 i 栋楼的教授的专业（如果有的话）。

输出：
- 第一行是一个整数 l，表示你选择的行程中的操作数量。
- 接下来的 l 行，每行包含一个命令：
- DRIVE x：前往编号为 x 的楼。
- PICKUP：从当前楼接上教授。
- DROPOFF：在当前楼放下乘客教授。

要求：
- 每栋楼最多访问一次。
- 在每个楼最多只能有一个放下的操作和一个接上的操作，并且先放下后接上。
- 在接上操作时，楼里必须有一个教授，并且摩托车上没有乘客。
- 在放下操作时，摩托车上必须有一个乘客。
- 行程结束后，每个有课程的楼都必须有一个相应专业的教授。

示例：
输入：
3
CM-
-MC

输出：
7
DRIVE 3
PICKUP
DRIVE 2
DROPOFF
PICKUP
DRIVE 1
DROPOFF

在这个例子中，你首先前往编号为 3 的楼，接上数学教授，然后放下他在编号为 2 的楼，接着接上计算机科学教授，最后在编号为 1 的楼放下她，完成行程。题目大意： 这个题目是关于一个校园里有 n 栋楼的问题。每栋楼可能安排了数学课、计算机课，或者两者都没有。每栋楼最多有一个教授，教授可能是数学专家或计算机科学专家。你有一个两座的摩托车，可以带你和最多一个乘客。你需要设计一个行程，使得每个安排了课程的楼都有相应的专家教授上课。你可以在每个楼最多访问一次，并且可以自由选择访问的顺序。 输入输出数据格式： 输入： - 第一行是一个整数 n (1 ≤ n ≤ 2000)，表示楼的数量。 - 第二行是一个长度为 n 的字符串，由字符 '-'、'C'、'M' 组成，第 i 个字符表示第 i 栋楼安排的课程的科目。'C' 表示计算机科学，'M' 表示数学，'-' 表示没有安排课程。 - 第三行也是一个长度为 n 的字符串，由字符 '-'、'C'、'M' 组成，第 i 个字符表示第 i 栋楼的教授的专业（如果有的话）。 输出： - 第一行是一个整数 l，表示你选择的行程中的操作数量。 - 接下来的 l 行，每行包含一个命令： - DRIVE x：前往编号为 x 的楼。 - PICKUP：从当前楼接上教授。 - DROPOFF：在当前楼放下乘客教授。 要求： - 每栋楼最多访问一次。 - 在每个楼最多只能有一个放下的操作和一个接上的操作，并且先放下后接上。 - 在接上操作时，楼里必须有一个教授，并且摩托车上没有乘客。 - 在放下操作时，摩托车上必须有一个乘客。 - 行程结束后，每个有课程的楼都必须有一个相应专业的教授。 示例： 输入： 3 CM- -MC 输出： 7 DRIVE 3 PICKUP DRIVE 2 DROPOFF PICKUP DRIVE 1 DROPOFF 在这个例子中，你首先前往编号为 3 的楼，接上数学教授，然后放下他在编号为 2 的楼，接着接上计算机科学教授，最后在编号为 1 的楼放下她，完成行程。