当然,您已经遇到过需要输出模 $$$10^9+7$$$、$$$10^9+9$$$ 或 $$$998244353$$$ 答案的问题。但是您是否遇到过必须打印对 $$$3$$$ 取模的答案的问题?
给您一个由 $$$n$$$ 个顶点组成的函数图,编号从 $$$1$$$ 到 $$$n$$$。它是一个有向图,其中每个顶点都有一个出射弧。该图以数组 $$$g_1, g_2, \dots, g_n$$$ 形式给出,其中 $$$g_i$$$ 表示有一条从 $$$i$$$ 到 $$$g_i$$$ 的弧。对于某些顶点,传出弧可能是自循环。
最初,图的所有顶点都用颜色 $$$1$$$ 着色。您可以执行以下操作:选择一个顶点和从 $$$1$$$ 到 $$$k$$$ 的颜色,然后为该顶点以及从该顶点可达的所有顶点着色。您可以执行此操作任意次数(甚至零次)。
您应该处理 $$$q$$$ 查询。该查询由三个整数$$$x$$$、$$$y$$$ 和$$$k$$$ 描述。对于每个查询,您应该:
- 分配 $$$g_x := y$$$;
- 然后计算给定值$$$k$$$的不同图形着色的数量(如果这两种着色中至少存在一个顶点着色为不同颜色,则两种着色不同);由于答案可能非常大,请将其打印出来 模 $$$3$$$.
请注意,在每个查询中,图的初始颜色都会重置(每个查询中所有顶点最初的颜色为 $$$1$$$)。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$g_1, g_2, \dots, g_n$$$ ($$$1 \le g_i \le n$$$)。
接下来是 $$$q$$$ 行。第 $$$i$$$ 行包含三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$k_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$1 \le k_i \le 10^9$$$)。
输出
对于每个查询,打印一个整数 - 给定值 $$$k$$$ 的不同图形着色的数量,以 $$$3$$$ 为模。
示例
输入复制
4 52 3 1 44 3 12 1 23 4 34 1 52 4 4
输出复制
1 2 0 2 1
输入复制
8 107 4 6 8 7 7 1 41 7 52 3 38 6 13 1 37 2 55 2 42 7 44 6 55 2 34 5 1
输出复制
1 0 1 0 2 1 1 2 0 1