配点 : 100 点
問題文
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
入力
输入是按以下格式从标准输入给出的。
N S T P A_1 A_2 \dots A_P Q B_1 B_2 \dots B_Q
出力
10^6 次操作的情况下都无法满足条件,-1 。
如果满足条件是可能的,请按照以下格式输出操作次数最少的操作序列。 1 输出一。
M U
这里 M 表示操作次数,U 表示操作序列的长度,
第 M 可以得到第 0, 1 组成的字符串。
U 可以得到第 i 第一个字母是 1 时,i 次操作表示从左起
将第 B_1,B_2,\dots,B_Q 张卡片的正反面全部翻转,0 表示什么都不做。
在第
入力例 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 。