pod

Între două maluri ale unei văi adânci s-a construit un pod suspendat format din $N$ bucăţi de scândură, legate cu liane. Vom considera că scândurile sunt numerotate de la $1$ la $N$, începând de pe malul pe care ne aflăm. În timp unele bucăţi de scândură s-au deteriorat, iar altele chiar au dispărut.

Pentru traversarea podului se ştie că:

• se pot face paşi doar de lungime $1$, $2$ sau $3$
• scândurile deteriorate sunt nesigure, deci pe ele şi de pe ele se pot face doar paşi de lungime $1$
• evident, nu se poate păşi pe o scândură care lipseşte

Cerință

Scrieţi un program care să determine numărul de modalităţi de traversare a podului (mai exact, de a ajunge pe celălalt mal), precum şi o soluţie de traversare, dacă o astfel de soluţie există.

Date de intrare

Fişierul de intrare pod.in are structura:

N
k s1 s2 ... sk
h d1 d2 ... dh

$N$ reprezintă numărul total de scânduri.

$k \ s_1 \ s_2 \ldots s_k$ reprezintă numărul de scânduri lipsă şi numerele lor de ordine.

$h \ d_1 \ d_2 \ldots d_h$ reprezintă numărul de scânduri deteriorate şi numerele lor de ordine.

Date de ieșire

Fişierul de ieşire pod.out va conţine pe prima linie valoarea $–1$ dacă nu este posibil să traversăm podul, respectiv numărul de posibilităţi de a traversa podul, dacă aceasta este posibil.

În cazul în care există soluţii, pe cea de a doua linie va fi afişată o astfel de soluţie, prin indicarea, în ordine, a scândurilor pe care se păşeşte, sub forma:

Nr
p1 p2 ... pm

$Nr$ reprezintă numărul total de posibilităţi.

$p_1 \ p_2 \ldots p_m$ reprezintă soluţia determinată, prin indicarea în ordine a scândurilor pe care se păşeşte.

Restricții și precizări

• $3 \leq N \leq 300$
• $0 \leq k, h \leq N$
• $\{ s_1, s_2, \ldots, s_k \} \subseteq \{ 2, \ldots N \}, \{ d_1, d_2, \ldots, d_h \} \subseteq \{ 1, 2, \ldots, N \}$
• $\{ s_1, s_2, \ldots, s_k \} \bigcap \{ d_1, d_2, \ldots, d_h \} = \varnothing$
• $Nr$ are cel mult 80 de cifre

Exemplul 1

pod.in

5
0
0

pod.out

24
3

Exemplul 2

pod.in

10
2 2 7
1 5

pod.out

48
3 6 8

Exemplul 3

pod.in

6
2 2 4
1 3

pod.out

-1