【魔怔】线上博弈。嗯哦挨癖。公平。

你是某国一名普通的想象学竞赛生。一场由某国想象学学会举办的全国想象学竞赛马上就要开始了。

某国的一个省份为了减少考试名额的浪费，决定对该省报名参加的初中生进行线上热身预赛。你是其中需要参加热身赛的一名选手。

既然是线上预赛，你就需要和想象学学会某省特派员进行心理博弈。具体地，现在有 10^9 道题，每道题的编号（从 1 到 10^9）可以代表其难度，编号越大，难度越大。可能有相同难度的题，但我们将其视为不同的题目。

你在先前打算为可能考察的 n 道题做准备，其编号为 a_i。比赛原有 m 道题目，其编号为 b_i。另外仍然有可能考察的 l 道题目，其编号为 c_i。

你和特派员轮流换题。每一方在一轮中会进行如下操作：

1. 不再去准备某一道题，即把 a_i 放入 c 中。
2. 可以考虑是否选择另一道题并对其做准备。你和特派员都希望难度尽量简单，并且特派员会一直注意你，所以选择的这道题只能在 c 中，且难度要比刚才放弃的那一道题低，也就是 c_j<a_i 或 c_j<b_i。

无法换题的一方会在这场线上博弈中落败。求哪一方会胜利。

下文假设 N=n+m+l，b 和 c 顺次依序插入到 a 后。

这场热身赛的题目是少的，所以你决定把所有可行的状态全部枚举，并进行状压。具体地，设 S 为记录状态的三进制数，从低到高的第 i 位为 0 则在 c 中，为 1 则在 a 中，为 2 则在 b 中。

为了提高效率，你考虑进行记忆化搜索，每次记录轮到哪一方 id（轮到你则 id=1，轮到特派员则 id=2）和当前的 S。如果当前这一方必胜，则 \text{dfs}(id,S)=1，否则该函数的返回值为 0。

显然，如果有一种可以达成的子状态使得 \text{dfs}(3-id,S')=0（其中 S' 为你或特派员操作后的新状态），则你就有必胜策略，返回 1，如果没有，则返回 0。由此可以枚举放弃的题目和重新拿到的题目，并进行处理，就得到了最终的答案。

你的代码。

回看这一过程，你发现了一个很可怕的事实。

你和特派员的全部博弈过程都是在线上举行的，公平性可想而知。在你看不见的地方，可能他们已经完全修改了难度。身为一名普通的选手，你只能按照规则行事，可他们却能打破选手的规则。你的代码看似求出了谁终获胜，可实际上，猎人和猎物的身份在你的背后已悄然转变。从某国的全国名义之上，高层的想象学竞赛虽然免费，可所谓之热身赛却已然又成某省收费之理由。

可面对这一切，你也无法说什么或者做什么。因为你也是想象学竞赛选手。