A32147.Ptorrweee

由于这是最后一题，所有没有故事背景。

这是 Elbisivid 给 Ytiroirp 出的一道题，需要你来帮帮 Ytiroirp。

---

给定一棵有根树，树根为 $1$，初始点权均为 $0$。

有 $q$ 次操作，形如

• 1 u x，表示将 $u$ 的子树内的节点 $v$ 的点权增加上 $a^{x+dis(u,v)}$，其中 $dis(u,v)$ 表示 $u,v$ 之间的距离。

• 2 u，求出节点 $u$ 的当前点权。

$a$ 是事先给定的，在询问中不会更改。答案对 $998244353$ 取模。

第一行两个正整数，分别表示 $n,q,a$；

接下来的 $n-1$ 行，每行两个整数，$u,v$ 表示树的一条边。

接下来的 $q$ 行，每行表示一个操作，可能是 1 u x 或者 2 u 的格式，含义参考题面。

对于每一个 2 操作，输出答案。

提示

此处的 $dis(u,v)$ 能否用深度差类似的形式表示出来？找找题面里的不变量。

数据范围

令 $p_i$ 表示 $i$ 的父亲节点

对于 $30\%$ 的数据，$n,q\le 1000$；

对于另外 $10\%$ 的数据，$p_i=1(2\le i\le n)$；

对于另外 $30\%$ 的数据，$p_i=i-1(2\le i \le n)$；

对于 $100\%$ 的数据，$n\le 200000,1\le a\le 998244352,0\le x\le 300$。