Little Maxim loves interesting problems. He decided to share one such problem with you. 

Initially there is an array a, consisting of n zeroes. The elements of the array are indexed, starting from 1. Then follow queries to change array a. Each query is characterized by two integers vi, ti. In the answer to the query we should make the vi-th array element equal ti (avi = ti; 1 ≤ vi ≤ n).

Maxim thinks that some pairs of integers (x, y) are good and some are not. Maxim thinks that array a, consisting of n integers, is lucky, if for all integer i, (1 ≤ i ≤ n - 1) the pair of integers (ai, ai + 1) — is good. Note that the order of numbers in the pairs is important, that is, specifically, (1, 2) ≠ (2, 1).

After each query to change array a Maxim wants to know, how many ways there are to replace all zeroes in array a with integers from one to three so as to make the resulting array (without zeroes) lucky. Of course, distinct zeroes can be replaced by distinct integers.

Maxim told you the sequence of queries and all pairs of integers he considers lucky. Help Maxim, solve this problem for him.

Input

The first line contains integers n and m (1 ≤ n, m ≤ 77777) — the number of elements in the array and the number of commands.

The next three lines contain matrix w, consisting only of zeroes and ones; the j-th number in the i-th of these lines — wi, j. If wi, j = 1 (1 ≤ i, j ≤ 3), then pair (i, j) is good, otherwise it is not good. Matrix does not have to be symmetric relative to the main diagonal.

Next m lines contain pairs of integers vi, ti (1 ≤ vi ≤ n, 0 ≤ ti ≤ 3) — the queries to change the array.

Output

Print m integers — the i-th number should equal to the number of ways to replace all zeroes in array a (changed after the i-th query) by integers from one to three so as to make the resulting array (without zeroes) lucky. Separate the numbers by whitespaces. As the answers can be rather large, print the remainder from dividing them by 777777777.

Examples

Input

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


Output

3
6
1
1
2
2
1
3
3
6
#include <bits/stdc++.h>
using namespace std;
const int MOD = 777777777;
const int UNDEF = -1;
const long long INF = 1e18;
template <typename T>
inline bool chkmax(T& aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T& aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
int rint();
char rch();
long long rlong();
const int MAXSEG = 77777 + 4;
int segn;
const int mk = 3;
typedef struct {
  int a[mk][mk];
} S;
S t[2 * MAXSEG];
S identity;
S combine(const S& lefts, const S& rights) {
  S res;
  for (int i = 0; i < mk; i++) {
    for (int j = 0; j < mk; j++) {
      long long ans = 0;
      for (int k = 0; k < mk; k++) {
        ans += lefts.a[i][k] * (long long)rights.a[k][j];
      }
      res.a[i][j] = ans % MOD;
    }
  }
  return res;
}
void build() {
  int n = segn;
  for (int i = n - 1; i > 0; --i) t[i] = combine(t[i << 1], t[i << 1 | 1]);
}
void modify(int p, const S& value) {
  int n = segn;
  for (t[p += n] = value; p >>= 1;) t[p] = combine(t[p << 1], t[p << 1 | 1]);
}
S query(int l, int r) {
  r++;
  int n = segn;
  S resl = identity, resr = identity;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l & 1) resl = combine(resl, t[l++]);
    if (r & 1) resr = combine(t[--r], resr);
  }
  return combine(resl, resr);
}
S mat[4];
void printmat(S got) {
  for (int x = 0; x < mk; x++) {
    for (int y = 0; y < mk; y++) {
      printf("%d ", got.a[x][y]);
    }
    printf("\n");
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n = rint(), m = rint();
  for (int x = 0; x <= 2; x++) {
    for (int y = 0; y <= 2; y++) {
      mat[0].a[x][y] = rint();
    }
  }
  for (int k = 0; k < mk; k++) identity.a[k][k] = 1;
  for (int t = 1; t <= 3; t++) {
    for (int y = 0; y <= 2; y++) {
      mat[t].a[t - 1][y] = mat[0].a[t - 1][y];
    }
  }
  segn = n - 1;
  for (int x = 0; x < n - 1; x++) t[segn + x] = mat[0];
  build();
  int last = 0;
  for (int i = 0; i < m; i++) {
    int pos = rint() - 1, val = rint();
    if (pos == n - 1) {
      last = val;
    } else {
      modify(pos, mat[val]);
    }
    auto got = query(0, n - 2);
    long long ans = 0;
    for (int x = 0; x < mk; x++) {
      for (int y = 0; y < mk; y++) {
        if (last == 0 || last - 1 == y) {
          ans += got.a[x][y];
        }
      }
    }
    ans %= MOD;
    if (n == 1) {
      if (last == 0)
        ans = 3;
      else
        ans = 1;
    }
    printf("%d\n", (int)ans);
  }
}
static char stdinBuffer[1024];
static char* stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char* stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int rint() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char rch() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
long long rlong() {
  readAhead(32);
  long long x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
