题目背景

飞花令启动！

请注意本题特别的时间限制。

数据中存在 $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。

5 5 2
10 20 30 40 50
5 10 15 20 25
5
11

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$。