Description

As shown in the figure, a rail yard has two shunting stations B and C. At the left entrance A, there are $n$ trains waiting to enter (from left to right labeled $a, b, c, d$), and on the right side is the exit D. On this segment, trains entering from A and passing through B and C can only move one-way from left to right, and shunting stations B and C have no limit on the number of cars they can hold.

You are given $n$ and a permutation of $n$ lowercase letters, which represents the sequence of train IDs from left to right formed at exit D. Output a sequence of operations, one per line, each being a letter sequence of the form $h, L, R$, where $h$ is a train ID, $L$ is the original position of $h$ (positions are denoted by $\verb!A,B,C,D!$), and $R$ is the new position. Otherwise, output NO to indicate that such a dispatch cannot be completed.

Input Format

An integer $n$ ($1 < n \le 15$) and a string consisting of $n$ lowercase letters.

Output Format

If it is feasible, output the shortest dispatch sequence. When there are multiple solutions, output the lexicographically smallest scheme with respect to the operation $(L, R)$. If it is not feasible, output NO.

3
cba

c A B
b A B
a A D
b B D
c B D

Hint

Translated by ChatGPT 5