题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXIV Olimpiada Informatyczna — III etap Rozdroża parzystości

Bajtazar 掌管拜托尼亚王国新设立的公国，辖内有 $n$ 座城市。公国尚在建设初期，尚未修筑任何道路。Bajtazar 规划了 $m$ 条双向道路，每条连接两座城市。若全部建成，可实现任意城市间连通。然而，他缺乏设计经验，道路规划效率低下，每条新路的建设难度远超之前所有道路之和。他估算第 $i$ 条路的建设成本为 $2^i$ 拜托币。

不幸的是，拜托尼亚掀起一股「奇偶」热潮，居民对道路数的奇偶性极度执着。部分城市的居民认为偶数道路象征和谐与平静，要求其城市连出的道路数为偶数；其他城市居民则视奇数为独立与活力的象征，要求道路数为奇数。

Bajtazar 需重新规划，选择部分道路，满足所有城市的奇偶要求，并尽量降低总成本。但拜托尼亚公共采购法有时要求剔除 $k-1$ 个最便宜的方案，因此他需构建满足居民要求的第 $k$ 便宜的道路网。注意，居民不再要求道路网连通所有城市，尽管原计划具备此特性，但奇偶要求可能与之冲突。

更糟的是，拜托尼亚议会频繁修改采购法，变更 $k$ 值，居民也常改变偏好，忽而崇尚偶数，忽而迷恋奇数。Bajtazar 必须随之调整规划。帮助他展现慷慨与高效的治理能力，适应居民多变的需求，设计应建的道路网！

输入格式

第一行包含两个整数 $n, m$ $(1 \leq n, m \leq 500000)$，分别表示城市数量和可建道路数量。

接下来的 $m$ 行描述道路，第 $i$ 行包含两个整数 $a_i, b_i$ $(1 \leq a_i, b_i \leq n, a_i \neq b_i)$，表示可建连接城市 $a_i$ 和 $b_i$ 的双向道路，成本为 $2^i$ 拜托币。每对城市至多出现一次。

下一行包含 $n$ 个整数 $p_1, \ldots, p_n$，若 $p_i=0$，第 $i$ 个城市居民偏好偶数道路数；若 $p_i=1$，偏好奇数。

下一行包含整数 $k$ $(1 \leq k \leq 10^{18})$，表示 Bajtazar 考虑第 $k$ 便宜的满足居民要求的道路网（$k=1$ 为最便宜）。不同方案成本均不同。

下一行包含整数 $q$ $(0 \leq q \leq 500000)$，表示查询数量，随后 $q$ 行描述查询。每行包含字符 $c$ 和整数 $v$：

• 若 $c=\texttt{M}$，城市 $v$ $(1 \leq v \leq n)$ 的居民改变偏好（偶变奇，奇变偶）。
• 若 $c=\texttt{K}$，采购法变更，Bajtazar 考虑第 $v$ $(1 \leq v \leq 10^{18})$ 便宜的道路网。
• 若 $c=\texttt{D}$，Bajtazar 询问当前道路网是否包含第 $v$ $(1 \leq v \leq m)$ 条路（成本 $2^v$）。

输出格式

第一行输出初始道路网（居民偏好变更前），包含 $m$ 个整数，第 $i$ 个为 $1$ 表示建第 $i$ 条路，为 $0$ 表示不建，保证存在合法方案。

接下来的行对应 $c=\texttt{D}$ 的查询。若当前道路网不存在（因居民偏好变更或方案不足被剔除），输出 $-1$；若存在，输出 $1$ 表示当前方案包含第 $v$ 条路，输出 $0$ 表示不包含。

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 0 0
1
-1
1
0

提示

样例 1 解释

有三座城市和三条路形成环。最便宜的道路网满足城市 $1,2$ 奇数、城市 $3$ 偶数要求，仅包含路 $1-2$（成本 $2$）。不存在仅一个城市有奇数道路的方案。城市 $1,3$ 奇数、城市 $2$ 偶数的方案有两种：较便宜的包含路 $1-2, 2-3$（成本 $2+4=6$），较贵的包含路 $1-3$（成本 $8$）。

附加样例

1. $n=6, m=15, q=50$，每对城市间有路，无 $\texttt{K}$ 类型查询。
2. $n=10, m=10, q=84$，路形成环，$\texttt{D}$ 类型查询时总有两种可行方案。
3. $n=101, m=150$，$50$ 个三角形，每相邻三角形共享一顶点，全为偶数要求，$k=2^{50}$，无查询。

详细子任务附加限制及分值如下表所示。