쉬운 하노이 문제

세 개의 기둥은 $0,1,2$번으로 번호가 붙어 있으며, $0$번 기둥이 가장 왼쪽 기둥이다. $N$개의 디스크는 큰 것부터 차례대로 $1,2,\cdots,N$번이다. 따라서 $1$번 디스크가 가장 크고 $N$번 디스크가 가장 작다.

하나의 상태는 길이 $N$의 수열 $P$로 나타낸다. $P_i$는 $i$번 디스크가 놓인 기둥의 번호이다. 한 기둥에 여러 디스크가 있으면 번호가 작은 디스크일수록 아래에 있는 것으로 본다.

한 번의 이동에서는 어떤 기둥의 가장 위에 있는 디스크 하나를 다른 기둥의 가장 위로 옮긴다. 이동 후 번호가 작은 디스크가 번호가 큰 디스크 위에 놓이면 안 된다. 즉, 큰 디스크를 작은 디스크 위로 옮길 수 없다.

목표 상태는 모든 디스크가 $0$번 기둥에 놓인 상태이다. 어떤 상태 $S$의 목표 거리는 $S$에서 목표 상태로 가기 위해 필요한 이동 횟수의 최솟값이다.

상태 $P$와 정수 $K$가 주어진다. $P$와 다른 상태 중에서 목표 거리가 $P$의 목표 거리와 같은 상태가 $K$개 이상 존재하는지 판단하여라. 존재한다면 그러한 상태를 정확히 $K$개 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ K$ $P_1\ P_2\ \cdots\ P_N$

$P$와 다른 상태 중에서 목표 거리가 $P$의 목표 거리와 같은 상태가 $K$개 미만이면 첫째 줄에 No를 출력한다.

그러한 상태가 $K$개 이상이면 첫째 줄에 Yes를 출력한다. 그 다음 $K$개의 줄에 걸쳐 조건을 만족하는 상태를 하나씩 출력한다.

각 상태는 다음과 같이 $N$개의 정수로 출력한다.

$Q_1\ Q_2\ \cdots\ Q_N$

여기서 $Q_i$는 $i$번 디스크가 놓인 기둥의 번호이며, $0 \leq Q_i \leq 2$를 만족해야 한다.

출력한 각 상태는 입력 상태 $P$와 달라야 하며, 출력한 상태들은 서로 달라야 한다. 또한 출력한 각 상태의 목표 거리는 $P$의 목표 거리와 같아야 한다. 가능한 답이 여러 가지라면 아무거나 출력해도 된다.

• $1 \leq N \leq 100\,000$.
• $1 \leq K \leq 100\,000$.
• $NK \leq 100\,000$.
• $0 \leq P_i \leq 2$ ($1 \leq i \leq N$).