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

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 50000$)

• $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 100000$)

• $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$

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