Comet OJ

C1579 [Contest #11]D-isaster

内存限制：256 MB 时间限制：1000 ms

题目描述

※ 简洁题意在分隔线下方

线段树掌心抵在墙上，纵横交错的纹路以其手掌为中心在四壁延展开来，随之一同蔓延的还有战前无形的紧张。

「我希望大家能将这张 $n$ 个点 $m$ 条边的地图铭记在心，尤其是每一个点的标号——我将其按照危险度从小到大的顺序编为 $1\sim n$ ，可以肯定的是，所有点都是联通的。因为这些位置在不久的将来便会成为你们执行任务的地点——」她停顿了一下，「或是生命终结的地点。」在座的众数据结构一言不发，凝神听着指挥官的安排。

「所以， splay ，这就是战前的情报工作？」一行小字从伸展树眼前掠过，她无须思索便得知这是替罪羊树传给她本体的询问。「没错。我们会被分组，深入敌军腹地。」她以同样的方式回答了替罪羊树。

「我会将各小队传送至不同地点。线段树已经计算出了每一队能探索区域的最大危险度，标记为该队的能力值。而你们需要做的，则是游走于你们能踏足的区域内，最后将信息回传。」一旁的女子起身道。线段树接着她的话继续说道：「根据估算，编号为 $i$ 的点在每一次行动中都会贡献 $a_i$ 的信息指数，而该次行动获取的总信息量为执行任务的小队能通过编号不大于该队能力值的点到达的所有点的信息指数乘积。当然，根据获得的结果，我们会适时地修改对某个 $a_i$ 的估算。」

额外的信息恰合时宜地在图上浮现。替罪羊树专注地分析着接下来的行动，读到伸展树传来的一条讯息：「我们一队，到时候要好好读题。」

你对这个种族的战前准备毫无兴趣，只想知道每次任务获取的信息量对 $998244353​$ 取模的值，也就是说——



简洁题意：

你需要支持对一张 $n$ 个点 $m$ 条边点带权的无向连通图进行以下两种操作：

  1. 修改点 $x$ 的点权。

  2. 询问从点 $x$ 出发只经过编号不大于 $y$ 的点能到达的所有点的点权之积取模 $998244353$。

输入格式

第一行 $3$ 个整数 $n, m, q$ ($1\le n, q \le 10^5, 1 \le m \le 2 \times 10^5$)，依序表示图的点数、边数、操作次数。

接下来一行 $n$ 个整数，第 $i$ 个数 $a_i$ ($1\le a_i\le 10^9$) 表示点 $i$ 的信息指数 (点权)。

接下来的 $m$ 行，每行两个整数 $u, v$ ，表示图中连结 $u, v$ 的一条无向边。保证此图连通。

接下来一行一个整数 $q$ ，表示。

再接下来的 $q$ 行，每行三个整数 $op, x, y$ ($1\le op\le 2, 1 \le x \le n$) 。

  • $op=1$ 时，表示询问从 $x$ 出发，只经过编号不大于 $y$ 的点能到达的所有点的点权之积取模 $998244353$ 。

  • $op=2$ 时，表示 $a_x$ 的值变为 $y$ ($1\le y \le 10^9$) 。

输出

对于每个 $op=1$ 的操作，输出一行包含一个整数表示从 $x$ 出发，只经过编号不大于 $y$ 的点能到达的所有点的点权之积取模 $998244353$，特别地，当 $x \gt y$ 时答案为 0。

样例

样例输入 1

3 2 2
2 3 3
1 2
2 3
1 2 2
1 3 2

样例输出 1

6
0

样例输入 2

3 7 9
5 3 2
1 1
2 2
3 3
3 2
2 3
3 1
3 1
1 2 2
1 2 3
1 3 2
2 1 1
1 2 2
1 2 3
1 3 3
2 1 1000000000
1 1 1

样例输出 2

3
30
0
3
6
6
1755647

提示