Lampade (lamp)

Per illuminare il salone delle IOI '98 si hanno a disposizione un set di N lampade colorate e numerate da 1 a N. Le lampade sono connesse a 4 pulsanti:

• Pulsante 1: quando viene premuto tutte le lampade cambiano il loro stato; quelle spente si accendono e quelle che sono accese si spengono.
• Pulsante 2: cambia lo stato delle lampade che hanno numero dispari.
• Pulsante 3: cambia lo stato delle lampade che hanno numero pari.
• Pulsante 4: cambia lo stato delle lampade che hanno numero nella forma 3k+1 con 0<=K, quindi 1, 4, 7,... .

Vi viene fornito il valore del contatore C e varie informazioni sullo stato finale di alcune lampade. Si richiede di scrivere un programma che determini tutte le possibili configurazioni finali delle N lampade in accordo con le informazioni fornite, senza ripetizioni.

File di input

Il file di input, di nome input.txt, contiene sulla prima riga il singolo intero N e sulla seconda il valore del contatore C. La terza riga contiene la lista delle lampade che sicuramente sono accese nella configurazione finale, mentre la riga sottostante (la quarta) contiene la lista dei numeri di lampade che sicuramente sono spente nella configurazione finale.

Non si possiedono informazioni sulle lampade il cui numero non compare in nessuna delle due liste. Queste potranno quindi essere accese o spente, nella configurazione finale. Per la terza e la quarta riga vale la regola che i numeri delle lampade che compaiono nella lista sono separati da spazio e terminati da un -1.

File di output

Il file di output, di nome output.txt, deve contenere tutte le possibili configurazioni delle lampade che rispettano le informazioni fornite nel file di input, senza ripetizioni. L'ordine con il quale le configurazioni vengono elencate non è rilevante. Ogni riga del file di output deve contenere N caratteri, senza separatori. Il carattere i-esimo rappresente lo stato dell'i-esima lampada in quella particolare configurazione e può essere uguale solo a 1 (che indica che la lampada è accesa) o 0 (lampada spenta).

Assunzioni

Si fanno le seguenti assunzioni:

• il tempo limite di esecuzione è fissato in 0.5 secondi;
• 10 <= N <= 400;
• 1 <= C <= 10000;
• il numero di lampade che si è sicuri siano accese nella configurazione finale è minore od uguale a 2;
• il numero di lampade che si è sicuri siano spente nella configurazione finale è minore od uguale a 2;
• esiste almeno una possibile configurazione finale delle lampade che rispetta i vincoli imposti.

Esempio di input/output

File input.txt

   10
   1
   -1
   7 -1

	

In questo caso ci sono 10 lampade e solo un bottone è stato premuto. La lampada n. 7 è spenta nella configurazione finale.

File output.txt

   
   0000000000
   0110110110
   0101010101
	

In questo caso ci sono tre possibili configurazioni finali:

• tutte le lampade sono sono spente;
• le lampade 1, 4, 7, 10 sono spente e le altre sono accese;
• le lampade 1, 3, 5, 7, 9, sono spente e le altre sono accese.