E. Счастливые массивы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Маленький Максим любит интересные задачи. Одной из таких задач он решил поделиться с Вами.

Изначально имеется массив a, состоящий из n нулей. Элементы массива индексируются, начиная с 1. Далее поступают запросы на изменение массива a. Каждый запрос характеризуются двумя целыми числами vi, ti. В ответ на запрос нужно сделать vi-тый элемент массива равным ti (avi = ti; 1 ≤ vi ≤ n).

Максим считает, что некоторые пары целых чисел (x, y) — хорошие, а некоторые — нет. Массив a, состоящий из n целых чисел, Максим считает счастливым, если для всех целых i, (1 ≤ i ≤ n - 1) пара целых чисел (ai, ai + 1) — хорошая. Обратите внимание, что порядок чисел в парах важен, то есть, в частности, (1, 2) ≠ (2, 1).

После каждого запроса на изменение массива a Максим хочет знать, сколько существует способов заменить все нули в массиве a на целые числа от одного до трех так, что полученный массив (без нулей) будет счастливым. Конечно, разные нули можно заменять на разные числа.

Максим сообщил Вам последовательность запросов, а также все пары чисел, которые он считает счастливыми. Помогите Максиму, решите для него эту задачу.

Входные данные

В первой строке заданы целые числа n и m (1 ≤ n, m ≤ 77777) — количество элементов в массиве и количество команд.

В следующих трех строках задана матрица w, состоящая только из нулей и единиц; j-тое число в i-той из этих строк — wi, j. Если wi, j = 1 (1 ≤ i, j ≤ 3), то пара (i, j) — хорошая, иначе — нет. Матрица не обязана быть симметричной относительно главной диагонали.

В следующих m строках заданы пары чисел vi, ti (1 ≤ vi ≤ n, 0 ≤ ti ≤ 3) — запросы на изменение массива.

Выходные данные

Выведите m целых чисел — i-тое число, должно быть равно количеству способов заменить все нули в массиве a (измененного после i-того запроса) на целые числа от одного до трех так, что полученный массив (без нулей) будет счастливым. Числа разделяйте пробельными символами. Так как ответы могут получаться достаточно большими, выводите их остаток от деления на 777777777.

Примеры
Входные данные
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
Выходные данные
3
6
1
1
2
2
1
3
3
6