AT_utpc2023_f.Flip or Not

有 $N$ 张卡片横向排列成一行。最初，如果字符串 $S$ 的第 $i$ 个字符为 1，则从左数第 $i$ 张卡片正面朝上，为 0 时反面朝上。

你可以进行至多 $10^6$ 次如下操作：

• 将最右边的一张卡片移动到最左边。如果被移动的卡片正面朝上，则将从左数第 $A_1,A_2,\dots,A_P$ 张卡片的正反面全部翻转。然后，可以选择将从左数第 $B_1,B_2,\dots,B_Q$ 张卡片的正反面全部翻转，或者什么都不做。

经过若干次操作后，你希望卡片的状态满足字符串 $T$ ——也就是说，如果 $T$ 的第 $i$ 个字符为 1，则从左数第 $i$ 张卡片正面朝上，为 0 时反面朝上。

请判断是否能在不超过 $10^6$ 次操作内满足条件。如果可以，请输出一种操作次数最小的操作序列。

输入从标准输入中读入，格式如下：

$N\ S\ T\ P\ A_1\ A_2\ \dots\ A_P\ Q\ B_1\ B_2\ \dots\ B_Q$

如果无论如何都无法在 $10^6$ 次以内达成要求，请输出 -1。

如果可以达成，请输出一组操作次数最小的方案：

$M\ U$

其中 $M$ 表示操作次数，$U$ 是由 0 和 1 组成的长度为 $M$ 的字符串。$U$ 的第 $i$ 个字符为 1 表示第 $i$ 次操作需要将从左数第 $B_1,B_2,\dots,B_Q$ 张卡片的正反面全部翻转；为 0 表示不翻转。

样例解释 1

在第 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

无论如何操作，都无法在 $10^6$ 次以内完成，所以输出 -1。

约束条件

• 输入的所有数值均为整数。
• $1 \leq N \leq 5000$
• $S, T$ 为长度为 $N$ 仅由 0, 1 组成的字符串
• $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$

由 ChatGPT 5 翻译