← 返回题目列表

Codeforces · 256/E

E. 幸运阵列

中文机器翻译题面 查看原题

小马克西姆喜欢有趣的问题。他决定与你分享一个这样的问题。

最初有一个数组 a,由 n 个零组成。数组的元素有索引,从1开始。然后按照查询更改数组a。每个查询由两个整数vi、ti 来表征。在查询的答案中,我们应该使第 vi 个数组元素等于 ti (avi = ti; 1 ≤ vi ≤ n)。

Maxim 认为有些整数对 (x, y) 是好的,有些则不是。 Maxim 认为由 n 个整数组成的数组 a 是幸运的,如果对于所有整数 i,(1 ≤ i ≤ n - 1) 整数对 (ai, ai + 1) — 就很好。请注意,数字对中的顺序很重要,即 (1, 2) ≠ (2, 1)。

在每次查询更改数组之后,Maxim 想知道有多少种方法可以用 1 到 3 的整数替换数组 a 中的所有零,以使结果数组(没有零)幸运。当然,不同的零可以用不同的整数代替。

Maxim 告诉你查询序列以及他认为幸运的所有整数对。帮助马克西姆,为他解决这个问题。

输入

第一行包含整数 n 和 m (1 ≤ n, m ≤ 77777) — 数组中的元素数量和命令数量。

接下来的三行包含矩阵 w,仅由 0 和 1 组成;第 i 行中的第 j 个数字 — wi, j。如果 wi, j = 1 (1 ≤ i, j ≤ 3),则pair(i, j)是好的,否则是不好的。矩阵不必相对于主对角线对称。

接下来的 m 行包含整数对 vi, ti (1 ≤ vi ≤ n, 0 ≤ ti ≤ 3) — 更改数组的查询。

输出

打印 m 个整数 — 第 i 个数字应该等于将数组 a 中的所有零(在第 i 个查询后更改)替换为 1 到 3 之间的整数的方法数,以使结果数组(没有零)幸运。用空格分隔数字。由于答案可能相当大,因此打印除以 777777777 所得的余数。

示例

输入 #1

3 10
1 1 0
1 0 0
1 1 1
1 1
1 3
2 2
3 0
2 1
3 0
3 1
2 0
3 1
1 0

输出 #1

3
6
1
1
2
2
1
3
3
6