P12677 Brooklyn Round 1 & NNOI Round 1 A - Flying Flower

飞花令启动！ #### 请注意本题特别的时间限制。 **数据中存在 $k$ 不是质数的情况，对于这样的询问回答 `Z`。**

小 X 和小 Z 玩了飞花令，想要将其变成数学，一共进行 $q$ 轮，规则如下： + 开始时选择质数 $k$ 作为关键数。 + 小 X 有一个长度为 $n$ 的序列 $a$，小 Z 有一个长度为 $m$ 的序列 $b$。 + 小 X 先手，小 Z 后手。 + 两人要从自己的序列中选择一个数满足其质因子含有 $k$ 且比上一个人报的数大的数报出（第一个数可以是质因子含有 $k$ 的任何一个数）。 + 无数可报的人输。 他想问你，如果两个人都采用最优策略，以这些 $k$ 作为关键数，谁能胜利？

第一行 $n,m,q$，含义如题面所示。 第二行 $n$ 个数，代表序列 $a$。 第三行 $m$ 个数，代表序列 $b$。 第 $4$ 至 $q + 3$ 行，每行一个数，代表 $k$。

$q$ 行，如果小 X 赢输出 `X`，否则输出 `Z`。

**本题采用捆绑测试。** + Subtask 1（40pts）：$1 \le n,m,q \le 10^3，1 \le a_i,b_i,k \le 10^3$。 + Subtask 2（20pts）：$k \le 10$。 + Subtask 3（20pts）：$q = 1$。 + Subtask 4（20pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le n,m,q \le 5 \times 10^5,1 \le a_i,b_i,k \le 8 \times 10^6$。