Byteasar 正在管理 Byteotia 王国中一个新成立的县。该县由 $n$ 个城镇和零条道路组成——这个县太新了，以至于还没有任何基础设施！Byteasar 的项目之一是修建 $m$ 条双向道路，每条道路直接连接一对城镇。如果该计划完全实施，每个城市都可以通过道路到达其他任何城市。然而，Byteasar 缺乏经验导致了巨大的低效：专家工程师估计，每修建一条后续道路的成本都比之前所有道路的成本总和还要高。具体来说，据报告，第 $i$ 条道路的建设成本恰好为 $2^i$ 拜特币（bythalers）。

由于预算有限，进展缓慢。事实上，Byteotia 流行起了一种新的时尚——市民们突然对奇偶性产生了痴迷。一些城镇的市民认为偶数象征着和谐、一致与和平，因此要求他们城镇发出的道路数量必须是偶数。与此同时，其余城镇的市民认为奇数象征着独立、个人主义和足智多谋，因此要求他们城镇发出的道路数量必须是奇数。

现在 Byteasar 必须提出一个新的道路网络项目，仅选择之前设计道路的一个子集，以满足所有市民的愿望。自然地，他打算最小化其成本。Byteotia 的公共招标法规定，剔除 $k-1$ 个最便宜的方案，因此 Byteasar 实际上是在寻找满足市民需求的第 $k$ 便宜的道路网络。注意，与 Byteasar 不同，他们只关心奇偶性，即这样的网络不需要连通所有城镇。

此外，Byteotia 的议会经常修改公共招标法，改变参数 $k$ 的值，而市民们也经常改变他们对奇偶性的看法（每个城镇独立变化），突然倾向于偶数而不是奇数，反之亦然。可怜的 Byteasar 必须根据每一种情况的变化来调整他的项目。通过告诉他应该建设哪些道路网络，来帮助他证明自己的慷慨、管理能力以及适应多变趋势的灵活性！

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 500\,000$)，分别表示城镇的数量和县内可能修建的潜在道路数量。

接下来的 $m$ 行描述了最初设计的道路，即可能修建的道路。第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示可以修建一条直接连接城镇 $a_i$ 和 $b_i$ 的双向道路，成本为 $2^i$ 拜特币。每对城镇在输入中最多出现一次。

下一行包含 $n$ 个整数 $p_1, \dots, p_n$，由空格分隔。如果 $p_i = 0$，则第 $i$ 个城镇的市民喜欢偶数；如果 $p_i = 1$，则意味着他们更喜欢奇数。

下一行包含一个整数 $k$ ($1 \le k \le 10^{18}$)，指定 Byteasar 最初应确定满足市民愿望的第 $k$ 便宜的道路网络（即当 $k=1$ 时，他应该找到最便宜的一个）。注意，每两个不同的网络成本各不相同。

下一行包含一个整数 $q$ ($0 \le q \le 500\,000$)，指定查询的数量，随后是描述这些查询的 $q$ 行。查询的描述由一个指定查询类型的字符 $c$ 和一个数字 $v$ 组成。如果 $c = \text{M}$，则第 $v$ 号城镇 ($1 \le v \le n$) 的市民刚刚改变了他们偏好的奇偶性。如果 $c = \text{K}$，则议会修改了法案，从现在起 Byteasar 应该确定第 $v$ 便宜的道路网络 ($1 \le v \le 10^{18}$)。最后，如果 $c = \text{D}$，意味着 Byteasar 在询问你第 $v$ 条道路 ($1 \le v \le m$)（即成本为 $2^v$ 的那条）是否属于当前所寻求的道路网络。

输出格式

在标准输出的第一行，应打印最初寻求的道路网络的描述，即在任何情况改变之前——你可以假设这样的网络总是存在的。描述应由 $m$ 个由空格分隔的整数组成，其中第 $i$ 个数字表示是否应修建第 $i$ 条道路，即如果应修建则为 $1$，否则为 $0$。后续的 $\text{D}$ 类型查询应在接下来的行中以相同的格式回答，但有以下例外：如果由于符合市民要求的不同网络数量不足而导致所需的道路网络不存在，则应打印 $-1$。注意，符合要求的网络数量甚至可能为 $0$。否则，如果所寻求的网络存在，则应像之前一样使用数字 $1$ 和 $0$，即分别表示该道路属于或不属于所述网络。

样例

样例输入 1

3 3
1 2
2 3
3 1
1 1 0
1
7
D 1
M 2
D 1
M 3
D 2
K 2
D 2

样例输出 1

1 0 0
1
-1
1
0

说明

对于该样例的解释：有三个城镇和三条道路，它们形成一个环。满足城镇 1 和 2 发出的道路数量均为奇数，城镇 3 发出的道路数量为偶数的最便宜网络，仅包含 1–2 道路（成本为 2）。不存在只有一个城市发出奇数条道路的网络。恰好有两个不同的网络使得城镇 1 和 3 发出的道路数量均为奇数（且城镇 2 发出的道路数量为偶数）：两个网络中较便宜的一个由道路 1–2 和 2–3 组成（总成本为 $2 + 4 = 6$），而较贵的一个由单条道路 1–3 组成（成本为 8）。

子任务

测试集由以下子集组成。在每个子集中，可能有多个测试组。