시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 53 25 22 44.000%

문제

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$
  • $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$
  • 입력으로 주어지는 모든 수는 정수다.

출력

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

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

예제 입력 1

4
15 0 0 0
3
& 1 2 1
& 1 3 12
| 3 4 31

예제 출력 1

1
15 17 12 19

첫 번째 자리에는 $15$세의 참가자가 이미 배치되어 있다. 두 번째, 세 번째, 네 번째 자리에 각각 $17$세, $12$세, $19$세의 참가자를 배치하면, $15 \operatorname{\&} 17 = 1$, $15 \operatorname{\&} 12 = 12$, $12 \operatorname{|} 19 = 31$ 이므로 모든 데이터를 만족한다. 이 예제에서는 이 배치 이외에 가능한 다른 배치는 존재하지 않는다.

예제 입력 2

3
0 0 0
3
| 1 2 24
| 2 3 24
| 3 1 24

예제 출력 2

0