#358 Easy Hanoi Problem

Statement

세 개의 기둥은 $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$ 의 목표 거리와 같아야 한다. 가능한 답이 여러 가지라면 아무거나 출력해도 된다.

Sample 1

Input

2 2
1 0

Output

Yes
1 1
2 0

입력 상태와 출력된 두 상태의 목표 거리는 모두 $3$ 이다. 출력된 두 상태는 입력 상태와 다르고 서로도 다르다.

Sample 2

Input

3 1
0 0 0

Output

목표 거리가 $0$ 인 상태는 목표 상태뿐이므로, 입력 상태와 다른 상태를 출력할 수 없다.