小马克西姆喜欢有趣的问题。他决定与你分享一个这样的问题。
最初有一个数组 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