Central de comutação

Time limit: 3000 msMemory limit: 256 MB

Uma central contém $n$ comutadores e $2n$ fios direcionados, numerados de $1$ a $2n$ . Cada fio sai de exatamente um comutador e entra em exatamente um comutador. Um fio pode sair e entrar no mesmo comutador, e vários fios podem conectar o mesmo par de comutadores.

Cada comutador tem duas entradas distintas, $a$ e $b$ , e duas saídas distintas, $c$ e $d$ . Ele admite duas configurações:

configuração 0: um sinal que chega pelo fio $a$ continua pelo fio $c$ , e um sinal que chega por $b$ continua por $d$ ; seu custo é $p$ ;
configuração 1: um sinal que chega por $a$ continua por , e um sinal que chega por continua por ; seu custo é .

Os custos são pagos uma única vez por comutador. Depois de configurar a central, as escolhas permanecem fixas.

Queremos que todos os fios pertençam a um único circuito: começando por qualquer fio e seguindo as conexões configuradas, o sinal deve percorrer os $2n$ fios, cada um exatamente uma vez, antes de voltar ao fio inicial.

Encontre uma configuração de custo total mínimo ou determine que isso é impossível.

Input

A primeira linha contém $n$ ( $1 \le n \le 200\,000$ ).

A $i$ -ésima das próximas $n$ linhas contém $a_i$ , , , , e (, , , ).

Output

Se não houver solução, imprima -1.

Caso contrário, imprima o menor custo total na primeira linha. Na segunda linha, imprima uma string com $n$ caracteres, em que o $i$ -ésimo caractere é 0 ou 1 e indica a configuração do comutador $i$ . Qualquer solução ótima será aceita.

Samples

Sample 1

Input

2
1 2 3 4 0 5
3 4 1 2 0 2

Output

2
01

Com essa configuração, os fios formam o circuito $1,3,2,4$ . A configuração 10 também produz um único circuito, mas custa $5$ .

Sample 2

Input

2
1 2 1 2 0 1
3 4 3 4 0 1

Output

-1

Não há conexões entre os fios do primeiro comutador e os do segundo.