#P18145. Flip or Not

Flip or Not

Flip or Not

有N张牌排成一行,位置从左到右编号1到N。初始时,第i张牌正面朝上当且仅当字符串S的第i个字符为1,否则反面朝上。

一次操作包含以下步骤,顺序固定:

  1. 把最右边的牌移到最左边。
  2. 如果刚才移动的牌正面朝上,则翻转此时从左数第A_1,...,A_P个位置上的所有牌。
  3. 选择翻转此时第B_1,...,B_Q个位置上的所有牌,或者什么也不做。

希望最终第i张牌正面朝上当且仅当T的第i个字符为1。判断能否在1000000次操作以内达到目标;若能,输出操作次数最少的一组方案。

输入格式

输入按下列格式给出:

N
S
T
P
A_1 A_2 ... A_P
Q
B_1 B_2 ... B_Q

满足1≤N≤5000;S、T均为长度N的01串,且S≠T;1≤P,Q≤N;两个位置列表各自严格递增,所有位置均在1到N之间。

输出格式

若无法在1000000次操作以内达到目标,输出-1。

否则输出两行:第一行为最少操作次数M,第二行为长度M的01串U。U的第i个字符为1表示第i次操作执行了步骤3的翻转,为0表示没有翻转。若有多个最短方案,输出任意一个。

样例 1

5
00001
00111
3
1 2 3
2
3 5
4
1001

第一次操作先把最右边的1移到最左边,得到10000;按A翻转后得到01100;再按B翻转后得到01001。之后三步依次得到01000、00100、00111。

样例 2

4
0110
1000
2
1 2
4
1 2 3 4
-1