問題文

N 枚のカードが横一列に並んでいます。 最初、文字列 S の i 文字目が 1 のとき左から i 枚目のカードは表を向いていて、0 のとき裏を向いています。

あなたは以下の操作を 10^6 回まで行うことができます。

• 一番右にあるカードを一番左に移動する。その後、移動させたカードが表を向いているなら左から A_1,A_2,\dots,A_P 枚目のカードの表裏を全て反転させる。そして、左から B_1,B_2,\dots,B_Q 枚目のカードの表裏を全て反転させるか、何もしないかのどちらかを選択する。

操作の結果、文字列 T の i 文字目が 1 のとき左から i 枚目のカードは表を向いていて、0 のとき裏を向いているようにしたいです。

10^6 回以下の操作により条件を満たすことができるかを判定し、条件を満たすことが可能な場合は操作回数が最小となるような操作列を 1 つ出力してください。

制約

• 入力される数値は全て整数
• 1 \leq N \leq 5000
• S, T は 0, 1 のみからなる長さ N の文字列
• S \neq T
• 1 \leq P, Q \leq N
• 1 \leq A_1 < A_2 < \dots < A_P \leq N
• 1 \leq B_1 < B_2 < \dots < B_Q \leq N

入力例 1

5
00001
00111
3
1 2 3
2
3 5

出力例 1

4
1001

1 度目の操作において、まず一番右のカードを一番左に移すとカードの状態は 10000 になり、移動させたカードが表を向いているため、左から A_1,A_2,A_3 枚目（1,2,3 枚目）のカードの表裏を全て反転させて 01100 になります。その後、左から B_1,B_2 枚目（3,5 枚目）のカードの表裏を全て反転させることを選択すれば 01001 になります。 以後も出力例に従って操作すると、2 回目の操作で 01000 に、3 回目の操作で 00100 に、4 回目の操作で 00111 になります。 これよりも操作回数が少ない方法は存在しないため、出力例は正しい出力です。

入力例 2

4
0110
1000
2
1 2
4
1 2 3 4

出力例 2

-1

どのように操作しても 10^6 回以下で条件を満たすことができないため、-1 を出力します。