Los persas están construyendo un circuito lógico simple en su taller. El circuito consiste de N alambres iniciales denotados por ~x_1 , x_2 , ..., x_n~ y ~m~ compuertas lógicos OR denotados con ~c_1, c_2, ...,c_m~. Cada compuerta tiene exactamente dos entradas y una salida. Cada una de las compuertas está conectada a un alambre inicial ~x_j~ o a la salida de otro elemento ~c_j~. Por supuesto, no existen ciclos en un circuito lógico y, además, que la entrada de ~c_j~ puede estar conectada a la salida de ~c_i~ solamente cuando ~i < j~.

Cada alambre inicial en el circuito puede tener el valor ~0~ ó ~1~, y el valor de la salida de cada elemento es el resultado de la operación lógica OR de sus entradas— el valor es ~0~ si los valores de ambas entradas son ~0~, de lo contrario es ~1~.

Los persas no conocen los valores iniciales de los alambres del inicio, pero con mediciones cuidadosas, ellos han determinado los valores de salida de algunos elementos. Encuentre los valores restantes de las salidas que pueden ser determinados sin ambiguamente basados en las mediciones.

Entrada

La primera línea de la entrada contiene los enteros positivos ~n~ y ~m~ — el número de alambres iniciales y el número de compuertas en el circuito. La siguiente línea contienen una cadena de exactamente ~m~ caracteres que describen los valores medidos de la salida de cada compuerta ~c_j~, o es igual a “~?~” si ellos no hicieron esa medición. La j-ésima de las siguientes ~m~ lineas contiene las etiquetas de las dos entradas del circuito ~c_j~, cada etiqueta es una etiqueta del alambre inicial en la forma “~x_i~” donde ~1 \le i \le n~, o una etiqueta del elemento “~c_i~” donde ~1 \le i < j~. Las dos entradas de los elementos ~c_j~ pueden ser la misma. Usted puede asumir que los valores medidos son mutuamente consistentes.

Salida

La primera línea de la salida tienen que contener una cadena de ~m~ caracteres – el j-ésimo carácter en la cadena tienen que corresponder al valor de la salida de ~c_j~ o será “~?~” si el valor no puede ser determinado sin ambigüedad.

Ejemplo 1 de Entrada

4 4           
10??
x1 x2
x2 x3
x3 x4
x1 c3

Ejemplo 1 de Salida

10?1

La figura corresponde al primer ejemplo de entrada.

Ejemplo 2 de Entrada

4 5            
11???
x1 x2
x3 x4
x1 x3
x2 x4
c3 c4

Ejemplo 2 de Salida

11??1

Evaluación

Subtarea Puntos Restricciones

1        7          ~n ≤ 15,   m ≤ 20~         

2        42         ~n ≤ 500,  m ≤ 500~        

3        51         ~n ≤ 10000, m ≤ 10000~