신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회

SUAPC의 성공에 힘입어, 연두는 “신촌지역 초중고등학생 프로그래밍 대회 동아리 연합 대회”의 개최를 기획하고 있다. 이 대회는 신촌의 초등학교/중학교/고등학교에 다니는 $8$세 ~ $19$세의 학생이라면 누구든 참가할 수 있다.

연두는 컴퓨터 과학을 기반으로 연구한 자신만의 풍수지리설과 사주팔자를 굉장히 맹신한다. 따라서 이번 대회가 성공적으로 개최되기 위해서는, 참가자들의 나이에 따른 자리 배치가 매우 중요하다고 믿는다. 연두가 음양비트론에 의거하여 만든 데이터들에는, $x$번째 자리와 $y$번째 자리에 앉은 참가자의 나이를 bitwise AND 또는 bitwise OR 했을 때 어떤 값이 나와야 하는지 적혀있다.

그런데 SUAPC 2021 Winter에 이어 이 대회에도 후원사로 참여한 카카오에서, 몇 개의 자리를 골라 각 자리마다 특정 나이의 참가자를 앉혀달라는 부탁을 해왔다. 후원사의 부탁을 거절하고 싶지는 않은지라, 연두는 나머지 빈자리에 적절한 나이의 참가자를 잘 배치하여 자신의 모든 데이터를 만족시킬 수 있을지 궁금해졌다. 연두는 이미 $8$세 이상 $19$세 이하의 많은 학생을 확보해놓았다. 대회 준비에 바쁜 연두를 대신하여 연두가 원하는 대로 자리를 배치해주자.

다음과 같이 입력이 주어진다.

$N$

$a\_1\ a\_2\\,\dots\ a\_N$

$M$

$t\_1\ x\_1\ y\_1\ z\_1$

$\dots$

$t\_M\ x\_M\ y\_M\ z\_M$

빈자리에 $8$세 이상 $19$세 이하의 참가자를 배치하여 연두의 모든 데이터를 만족시킬 수 있다면, 첫 번째 줄에 $1$을 출력한다. 그다음 줄에, $1$번째, $2$번째, $\dots$, $N$번째 자리에 앉을 참가자의 나이를 공백으로 구분하여 출력한다. 그런 배치가 여러 가지면 그 중 아무거나 하나를 출력한다.

만약 그런 배치가 존재하지 않는다면, 대신에 첫 번째 줄에 $0$을 출력한다.

• $N$은 자리의 개수이다. ($2 \le N \le 50\\,000$)

• $a\_i = 0$ 또는 $8 \le a\_i \le 19$

  • $a\_i = 0$이면, 현재 $i$번째 자리는 빈자리다.
  • $8 \le a\_i \le 19$면, $i$번째 자리에 앉을 참가자의 나이가 $a\_i$다.

• $M$은 연두의 데이터의 개수다. ($1 \le M \le 100\\,000$)

• $t\_i =$ & 또는 $t\_i =$ |

  • $t\_i =$ &면,  $x\_i$번째 자리에 앉은 참가자의 나이와 $y\_i$번째 자리에 앉은 참가자의 나이의 bitwise AND가 $z\_i$여야 한다.
  • $t\_i =$ |면,  $x\_i$번째 자리에 앉은 참가자의 나이와 $y\_i$번째 자리에 앉은 참가자의 나이의 bitwise OR이 $z\_i$여야 한다.

• $1 \le x\_i, y\_i \le N$, $x\_i \ne y\_i$

• $0 \le z\_i \le 31$

• 입력으로 주어지는 모든 수는 정수다.