CF2104G Modulo 3

Surely, you have seen problems which require you to output the answer modulo $ 10^9+7 $ , $ 10^9+9 $ , or $ 998244353 $ . But have you ever seen a problem where you have to print the answer modulo $ 3 $ ? You are given a functional graph consisting of $ n $ vertices, numbered from $ 1 $ to $ n $ . It is a directed graph, in which each vertex has exactly one outgoing arc. The graph is given as the array $ g_1, g_2, \dots, g_n $ , where $ g_i $ means that there is an arc that goes from $ i $ to $ g_i $ . For some vertices, the outgoing arcs might be self-loops. Initially, all vertices of the graph are colored in color $ 1 $ . You can perform the following operation: select a vertex and a color from $ 1 $ to $ k $ , and then color this vertex and all vertices that are reachable from it. You can perform this operation any number of times (even zero). You should process $ q $ queries. The query is described by three integers $ x $ , $ y $ and $ k $ . For each query, you should: - assign $ g_x := y $ ; - then calculate the number of different graph colorings for the given value of $ k $ (two colorings are different if there exists at least one vertex that is colored in different colors in these two colorings); since the answer can be very large, print it modulo $ 3 $ . Note that in every query, the initial coloring of the graph is reset (all vertices initially have color $ 1 $ in each query).

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n, q \le 2 \cdot 10^5 $ ). The second line contains $ n $ integers $ g_1, g_2, \dots, g_n $ ( $ 1 \le g_i \le n $ ). The $ q $ lines follow. The $ i $ -th line contains three integers $ x_i $ , $ y_i $ and $ k_i $ ( $ 1 \le x_i, y_i \le n $ ; $ 1 \le k_i \le 10^9 $ ).

For each query, print a single integer — the number of different graph colorings for the given value of $ k $ , taken modulo $ 3 $ .