题目背景

明日香正在对战 EVA 量产机。

所有量产机可以视为一张无向图，不同的量产机间时而相连，时而相离。

装备了 N2 机关的量产机在不断变强。具体地，第 $i$ 个量产机的战力值会变成自己的平方。处于一个联通块的量产机战力变化次数相同。

失去电源的明日香只剩下五分钟。为了更好地应对量产机，她想尽快知道每个由量产机构成的联通块战力之和。你能帮助她吗？

题目描述

现有函数 $f$ 和 $g$，其中 $f(x)=x^2$，$g_k(x)$ 为 $f$ 复合 $k$ 次的结果。
换而言之，$g_k(x)=x^{2^k}$。

给定 $n$ 个点 $m$ 条边的无向图 $G$ 以及每个点 $i$ 的权值 $a_i$，要你处理接下来的 $q$ 个操作。
操作有三种，操作从 $1$ 到 $3$ 编号。点从 $1$ 到 $n$ 编号。

• 1 x y 代表在 $x$ 和 $y$ 之间添加一条无向边 $(x,y)$。保证边 $(x,y)$ 原本不存在。
• 2 x y 代表删除边 $(x,y)$，保证边 $(x,y)$ 原本存在。
• 3 x k 代表查询 $x$ 所在的联通块 $S$ 中，$\sum_{i \in S} g_k(a_i)$ 的值。

由于答案很大，请输出答案对 $998244353$ 取模的结果。

输入格式

第一行三个整数 $n$, $m$, $q$，代表点数、边数、操作数。

接下来 $n$ 行，每行一个整数，第 $(i+1)$ 行的整数 $a_i$ 表示节点 $i$ 的权值。

接下来 $m$ 行，每行两个整数，第 $(i+n+1)$ 行的整数 $u_i, v_i$ 表示一条无向边 $(u_i,v_i)$。

接下来 $q$ 行，每行三个整数，分别代表操作类型和操作所需的量。

输出格式

对于每一个 $3$ 号操作，你须输出一行一个整数，表示 $x$ 所在的联通块 $S$ 中，$\sum_{i \in S} g_k(a_i)$ 的值。

样例

Input 1

5 3 9
1 2 3 4 5
1 3
2 3
4 5
3 1 2
3 4 1
1 1 2
1 4 3
3 5 3
2 1 3
2 2 3
3 2 1
3 4 1

Output 1

98
41
462979
5
50

数据范围

【子任务】

对于全部的测试点，保证：

• $1 \leq n \leq 10^5$，$1 \leq m, q \leq 2 \times 10^5$，$1 \leq u_i, v_i \leq n$，$0 \leq k \leq 10^9$，$1 \leq a_i < 998244353$。
• 对于操作 $1, 2$，保证 $1 \leq x, y \leq n$。
• 对于操作 $3$，保证 $1 \leq x \leq n$，$0 \leq k \leq 10^9$。
• 保证给定的图没有重边和自环。

• 特殊性质 A：保证不存在 $2$ 操作。
• 特殊性质 B：保证 $k \leq 20$。
• 特殊性质 C：保证每个联通块是一棵树。

样例解释

【样例 2】

见选手目录下的 evangelion/evangelion2.in 与 evangelion/evangelion2.ans。
该组样例满足测试点 $3 \sim 5$ 的限制。

【样例 3】

见选手目录下的 evangelion/evangelion3.in 与 evangelion/evangelion3.ans。
该组样例满足测试点 $6 \sim 8$ 的限制。

【样例 4】

见选手目录下的 evangelion/evangelion4.in 与 evangelion/evangelion4.ans。
该组样例满足测试点 $11 \sim 18$ 的限制。

【样例 5】

见选手目录下的 evangelion/evangelion5.in 与 evangelion/evangelion5.ans。
该组样例满足测试点 $19 \sim 25$ 的限制。