CF2104G.Modulo 3

给定基环内向森林，每个点有且仅有一条出边 $g_i$，可能有自环。

所有点的初始颜色均为 $1$，你可以执行如下操作任意次（可以为零次）：

• 选择一个顶点 $u \in [1,n]$，再选择一种颜色 $c \in [1,k]$，将 $u$ 能到达的所有点（包括 $u$ 本身）染成颜色 $c$。

你需要求出，最终能形成的不同的图的数量，答案对 $3$ 取模。

两个图不同，当且仅当存在一个编号为 $i$ 的节点，它的颜色在两图中不同。

现在有 $q$ 次修改操作，每次给定 $x,y,k$：

• 将 $g_x$ 修改为 $y$。
• 对于本次输入的 $k$，输出答案，对 $3$ 取模。

对 $g_x$ 的修改操作是永久的，对后面有影响。但是在每次询问答案时，所有顶点的初始颜色都是 $1$。

第一行包含两个整数 $n$ 和 $q$。

第二行包含 $n$ 个整数 $g_1, g_2, \dots, g_n$。

接下来是 $q$ 行，第 $i$ 行包含三个整数 $x_i$ 、 $y_i$ 和 $k_i$ （$1 \le k_i \le 10^9$ ）。

共 $q$ 行，每行一个在 $[0,3)$ 的整数。

$1 \le n, q \le 2 \times 10^5$。