기계 인형

기계 인형은 특정한 동작 순서를 자동으로 반복하는 인형입니다. 일본에서는 옛날부터 많은 기계 인형이 만들어졌습니다.

기계 인형의 동작은 장치로 이루어진 회로가 제어합니다. 장치들은 관으로 연결되어 있습니다. 각 장치에는 한두 개의 출구가 있고, 입구는 개수에 제한 없이 (0개일 수도 있습니다) 있습니다. 각 관은 어떤 장치의 출구와, 같은 장치 또는 다른 장치의 입구를 잇습니다. 각 입구에는 정확히 하나의 관이 연결되고, 각 출구에도 정확히 하나의 관이 연결됩니다.

장치 하나에 공을 놓으면 공이 회로 안을 이동합니다. 매 단계에서 공은 현재 장치의 출구 중 하나로 빠져나가고, 그 출구에 연결된 관을 따라 가서 관의 반대편 장치로 들어갑니다.

장치에는 원점, 트리거, 스위치의 세 종류가 있습니다. 원점은 하나, 트리거는 $M$개, 스위치는 $S$개입니다 ($S$는 0일 수 있습니다). $S$의 값은 직접 정해야 합니다.

원점은 공이 처음 놓이는 장치입니다. 출구가 하나 있으며 일련번호는 0입니다.

트리거는 공이 들어올 때마다 인형이 특정한 동작을 하게 만듭니다. 트리거마다 출구가 하나 있습니다. 트리거의 일련번호는 1부터 $M$까지입니다.

스위치에는 'X'와 'Y'라고 부르는 출구가 두 개 있습니다. 스위치의 상태는 'X' 또는 'Y'입니다. 공이 스위치에 들어가면 현재 상태에 해당하는 출구로 빠져나가고, 그 뒤 스위치는 반대 상태로 바뀝니다. 처음에는 모든 스위치가 'X' 상태입니다. 스위치의 일련번호는 -1부터 -$S$까지입니다.

$M$과 길이가 $N$인 수열 $A$가 주어집니다. $A$의 각 원소는 트리거의 일련번호입니다. 같은 트리거가 $A$에 여러 번 나타날 수 있고, 한 번도 나타나지 않을 수도 있습니다. 다음 조건을 모두 만족하는 회로를 만드세요.

• 공은 몇 단계 뒤에 원점으로 돌아온다.
• 공이 처음 원점으로 돌아왔을 때, 모든 스위치는 'X' 상태이다.
• 공이 처음 원점으로 돌아오기 전까지 정확히 $N$개의 트리거에 들어가며, 들어간 순서대로 트리거의 일련번호는 $A_0, A_1, \ldots, A_{N-1}$이다.
• 공이 처음 원점으로 돌아오기 전까지 모든 스위치에서 일어난 상태 변화의 총횟수를 $P$라고 하면, $P$는 20,000,000을 넘지 않는다.

또한 스위치를 너무 많이 사용하지 않으려고 합니다.

제한

• $1 \le M \le 100000$
• $1 \le N \le 200000$
• $1 \le A_k \le M$ ($0 \le k \le N-1$)