Sinchon Regional Middle and High School Student Programming Contest Club Joint Competition

Following the success of SUAPC, Yeondu is planning the "Sinchon Regional Middle and High School Student Programming Contest Club Joint Competition". Any student aged $8$ to $19$ who attends an elementary, middle, or high school in Sinchon can take part.

Yeondu firmly believes in his own feng shui and Four Pillars theories, which are based on computer science. He thinks the seating arrangement by age is critical to a successful contest. The data he built from his Yin-Yang Bitron theory states, for the seats at positions $x$ and $y$, the value the bitwise AND or bitwise OR of the two participants' ages must produce.

Kakao, which joined SUAPC 2021 Winter and is also a sponsor of this contest, asked for a favor. They want specific ages seated at a few chosen seats. Yeondu does not want to refuse the sponsor. He wants to know whether the remaining empty seats can be filled with suitable ages so that all of his data is satisfied. He already has many students aged $8$ to $19$. Arrange the seats for him while he is busy preparing the contest.

The input is given in the following format.

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

If you can fill the empty seats with participants aged $8$ to $19$ so that all of Yeondu's data is satisfied, print $1$ on the first line. On the next line, print the ages of the participants seated at seat $1$, seat $2$, $\dots$, seat $N$, separated by spaces. If several arrangements are valid, print any one of them.

If no such arrangement exists, print $0$ on the first line.

• $N$ is the number of seats. ($2 \le N \le 50000$)

• $a_i = 0$ or $8 \le a_i \le 19$

  • If $a_i = 0$, seat $i$ is empty.
  • If $8 \le a_i \le 19$, the participant seated at seat $i$ is $a_i$ years old.

• $M$ is the number of data items. ($1 \le M \le 100000$)

• $t_i$ is & or |.

  • If $t_i$ is &, the bitwise AND of the ages of the participants at seats $x_i$ and $y_i$ must be $z_i$.
  • If $t_i$ is |, the bitwise OR of the ages of the participants at seats $x_i$ and $y_i$ must be $z_i$.

• $1 \le x_i, y_i \le N$, $x_i \ne y_i$

• $0 \le z_i \le 31$

• All numbers in the input are integers.