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;
template <typename T, typename U>
std::istream &operator>>(std::istream &i, pair<T, U> &p) {
  i >> p.first >> p.second;
  return i;
}
template <typename T>
std::istream &operator>>(std::istream &i, vector<T> &t) {
  for (auto &v : t) {
    i >> v;
  }
  return i;
}
template <typename T, typename U>
std::ostream &operator<<(std::ostream &o, const pair<T, U> &p) {
  o << p.first << ' ' << p.second;
  return o;
}
template <typename T>
std::ostream &operator<<(std::ostream &o, const vector<T> &t) {
  if (t.empty()) o << '\n';
  for (size_t i = 0; i < t.size(); ++i) {
    o << t[i] << " \n"[i == t.size() - 1];
  }
  return o;
}
template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using maxheap = priority_queue<T, vector<T>, less<T>>;
template <typename T>
bool in(T a, T b, T c) {
  return a <= b && b < c;
}
unsigned int logceil(int first) {
  return 8 * sizeof(int) - __builtin_clz(first);
}
namespace std {
template <typename T, typename U>
struct hash<pair<T, U>> {
  hash<T> t;
  hash<U> u;
  size_t operator()(const pair<T, U> &p) const {
    return t(p.first) ^ (u(p.second) << 7);
  }
};
}  // namespace std
template <typename T, typename F>
T bsh(T l, T h, const F &f) {
  T r = -1, m;
  while (l <= h) {
    m = (l + h) / 2;
    if (f(m)) {
      l = m + 1;
      r = m;
    } else {
      h = m - 1;
    }
  }
  return r;
}
template <typename F>
double bshd(double l, double h, const F &f, double p = 1e-9) {
  unsigned int r = 3 + (unsigned int)log2((h - l) / p);
  while (r--) {
    double m = (l + h) / 2;
    if (f(m)) {
      l = m;
    } else {
      h = m;
    }
  }
  return (l + h) / 2;
}
template <typename T, typename F>
T bsl(T l, T h, const F &f) {
  T r = -1, m;
  while (l <= h) {
    m = (l + h) / 2;
    if (f(m)) {
      h = m - 1;
      r = m;
    } else {
      l = m + 1;
    }
  }
  return r;
}
template <typename F>
double bsld(double l, double h, const F &f, double p = 1e-9) {
  unsigned int r = 3 + (unsigned int)log2((h - l) / p);
  while (r--) {
    double m = (l + h) / 2;
    if (f(m)) {
      h = m;
    } else {
      l = m;
    }
  }
  return (l + h) / 2;
}
template <typename T>
T gcd(T a, T b) {
  if (a < b) swap(a, b);
  return b ? gcd(b, a % b) : a;
}
template <typename T>
class vector2 : public vector<vector<T>> {
 public:
  vector2() {}
  vector2(size_t a, size_t b, T t = T())
      : vector<vector<T>>(a, vector<T>(b, t)) {}
};
template <typename T>
class vector3 : public vector<vector2<T>> {
 public:
  vector3() {}
  vector3(size_t a, size_t b, size_t c, T t = T())
      : vector<vector2<T>>(a, vector2<T>(b, c, t)) {}
};
template <typename T>
class vector4 : public vector<vector3<T>> {
 public:
  vector4() {}
  vector4(size_t a, size_t b, size_t c, size_t d, T t = T())
      : vector<vector3<T>>(a, vector3<T>(b, c, d, t)) {}
};
template <typename T>
class vector5 : public vector<vector4<T>> {
 public:
  vector5() {}
  vector5(size_t a, size_t b, size_t c, size_t d, size_t e, T t = T())
      : vector<vector4<T>>(a, vector4<T>(b, c, d, e, t)) {}
};
template <unsigned int N>
class Field {
  inline unsigned int pow(unsigned int a, unsigned int p) {
    unsigned int r = 1, e = a;
    while (p) {
      if (p & 1) {
        r = ((unsigned long long)r * e) % N;
      }
      e = ((unsigned long long)e * e) % N;
      p >>= 1;
    }
    return r;
  }
  inline unsigned int inv(unsigned int a) { return pow(a, N - 2); }

 public:
  inline Field(int first = 0) : v(first) {}
  inline Field<N> pow(int p) { return (*this) ^ p; }
  inline Field<N> operator^(int p) { return {(int)pow(v, (unsigned int)p)}; }
  inline Field<N> &operator+=(const Field<N> &o) {
    if ((long long)v + o.v >= N)
      v += o.v - N;
    else
      v += o.v;
    return *this;
  }
  inline Field<N> &operator-=(const Field<N> &o) {
    if (v < o.v)
      v -= o.v - N;
    else
      v -= o.v;
    return *this;
  }
  inline Field<N> &operator*=(const Field<N> &o) {
    v = (unsigned long long)v * o.v % N;
    return *this;
  }
  inline Field<N> &operator/=(const Field<N> &o) { return *this *= inv(o.v); }
  inline Field<N> operator+(const Field<N> &o) const {
    Field<N> r{*this};
    return r += o;
  }
  inline Field<N> operator-(const Field<N> &o) const {
    Field<N> r{*this};
    return r -= o;
  }
  inline Field<N> operator*(const Field<N> &o) const {
    Field<N> r{*this};
    return r *= o;
  }
  inline Field<N> operator/(const Field<N> &o) const {
    Field<N> r{*this};
    return r /= o;
  }
  inline Field<N> operator-() {
    if (v)
      return {(int)(N - v)};
    else
      return {0};
  };
  inline Field<N> &operator++() {
    ++v;
    if (v == N) v = 0;
    return *this;
  }
  inline Field<N> operator++(int) {
    Field<N> r{*this};
    ++*this;
    return r;
  }
  inline Field<N> &operator--() {
    --v;
    if (v == -1) v = N - 1;
    return *this;
  }
  inline Field<N> operator--(int) {
    Field<N> r{*this};
    --*this;
    return r;
  }
  inline bool operator==(const Field<N> &o) const { return o.v == v; }
  inline bool operator!=(const Field<N> &o) const { return o.v != v; }
  inline explicit operator unsigned int() const { return v; }
  inline static vector<Field<N>> fact(int t) {
    vector<Field<N>> F(t + 1, 1);
    for (int i = 2; i <= t; ++i) {
      F[i] = F[i - 1] * i;
    }
    return F;
  }
  inline static vector<Field<N>> invfact(int t) {
    vector<Field<N>> F(t + 1, 1);
    Field<N> X{1};
    for (int i = 2; i <= t; ++i) {
      X = X * i;
    }
    F[t] = 1 / X;
    for (int i = t - 1; i >= 2; --i) {
      F[i] = F[i + 1] * (i + 1);
    }
    return F;
  }

 private:
  unsigned int v;
};
template <unsigned int N>
istream &operator>>(std::istream &is, Field<N> &f) {
  unsigned int v;
  is >> v;
  f = v;
  return is;
}
template <unsigned int N>
ostream &operator<<(std::ostream &os, const Field<N> &f) {
  return os << (unsigned int)f;
}
template <unsigned int N>
Field<N> operator+(int i, const Field<N> &f) {
  return Field<N>(i) + f;
}
template <unsigned int N>
Field<N> operator-(int i, const Field<N> &f) {
  return Field<N>(i) - f;
}
template <unsigned int N>
Field<N> operator*(int i, const Field<N> &f) {
  return Field<N>(i) * f;
}
template <unsigned int N>
Field<N> operator/(int i, const Field<N> &f) {
  return Field<N>(i) / f;
}
struct Ring {
  static int div(int p, int q, int N) {
    long long t = 0, nt = 1, r = N, nr = q;
    while (nr) {
      long long q = r / nr;
      t -= q * nt;
      r -= q * nr;
      swap(t, nt);
      swap(r, nr);
    }
    t = (t < 0) ? t + N : t;
    r = (r < 0) ? r + N : r;
    if (gcd(p, N) % r) {
      return 0;
    }
    return (int)(((long long)t * (long long)p / r) % N);
  }
};
template <typename T>
class Matrix {
 public:
  Matrix(size_t R, size_t C, T t = T(0))
      : R(R), C(C), A(R, vector<T>(C, t)), def(t) {}
  Matrix(const vector<vector<T>> &a, T t = T(0))
      : R(a.size()), C(a[0].size()), A(a), def(t) {}
  Matrix(const initializer_list<vector<T>> &a, T t = T(0))
      : R(a.size()), C(a.begin()->size()), A(a), def(t) {}
  size_t rows() const { return R; }
  size_t columns() const { return C; }
  bool isSquare() const { return R * C; }
  bool isIdentity() const {
    for (int i = 0; i < min(R, C); ++i) {
      for (int j = 0; j < min(R, C); ++j) {
        if (i == j && A[i][j] != 1) return false;
        if (i != j && A[i][j] != 0) return false;
      }
    }
    return true;
  }
  void addColumnsRight(size_t add, T t = T()) {
    for (int i = 0; i < R; ++i) {
      A[i].resize(C + add);
      for (size_t j = C; j < C + add; ++j) A[i][j] = t;
    }
    C += add;
  }
  void removeColumnsLeft(size_t rem) {
    for (size_t i = 0; i < R; ++i)
      A[i].erase(A[i].begin(),
                 rem > A[i].size() ? A[i].end() : A[i].begin() + rem);
  }
  T determinant() const {
    if (!isSquare()) {
      throw std::runtime_error(
          "Cannot compute determinant of a rectangular matrix");
    }
    Matrix<T> tmp(*this);
    T ans = tmp.toReducedRowEchelon();
    if (tmp.isIdentity())
      return ans;
    else
      return 0;
  }
  vector<T> solveFor(const vector<T> &b) {
    if (!isSquare()) {
      throw std::runtime_error("Cannot solve a rectangular matrix");
    }
    if (b.size() != R)
      throw new std::runtime_error(
          "Unable to solve linear equation, dimensions do not match");
    Matrix<T> tmp(*this);
    for (int i = 0; i < R; ++i) tmp.A[i].push_back(b[i]);
    ++tmp.C;
    tmp.toReducedRowEchelon();
    if (!tmp.isIdentity())
      throw std::runtime_error("Cannot solve a singular matrix");
    vector<T> Ans(R);
    for (int j = 0; j < R; ++j) Ans[j] = tmp.A[j].back();
    return Ans;
  }
  Matrix<T> power(unsigned long long N) {
    if (!isSquare()) {
      throw std::runtime_error(
          "Cannot compute determinant of a rectangular matrix");
    }
    Matrix<T> ans(R, R, 0), pow = *this;
    for (unsigned int r = 0; r < R; ++r) ans[r][r] = 1;
    while (N) {
      if (N & 1) ans = ans * pow;
      N >>= 1;
      pow = pow * pow;
    }
    return ans;
  }
  Matrix<T> &operator+=(const Matrix<T> &m) {
    if (R != m.R)
      throw std::runtime_error("Cannot add matrices of different height");
    if (C != m.C)
      throw std::runtime_error("Cannot add matrices of different width");
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < C; ++j) {
        A[i][j] += m.A[i][j];
      }
    }
    return *this;
  }
  Matrix<T> &operator-=(const Matrix<T> &m) {
    if (R != m.R)
      throw std::runtime_error("Cannot substract matrices of different height");
    if (C != m.C)
      throw std::runtime_error("Cannot substract matrices of different width");
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < C; ++j) {
        A[i][j] -= m.A[i][j];
      }
    }
    return *this;
  }
  Matrix<T> operator*(const Matrix<T> &m) const {
    if (C != m.R)
      throw std::runtime_error("Matrices incompatible for multiplication");
    Matrix<T> Ans(R, m.C, T(0));
    for (int i = 0; i < R; ++i) {
      for (int j = 0; j < m.C; ++j) {
        for (int k = 0; k < C; ++k) {
          Ans[i][j] += A[i][k] * m.A[k][j];
        }
      }
    }
    return Ans;
  }
  vector<T> operator*(const vector<T> &m) const {
    if (C != m.size())
      throw std::runtime_error(
          "Matric and vector incompatible for multiplication");
    vector<T> ans(R, def);
    for (unsigned int r = 0; r < R; ++r) {
      for (unsigned int c = 0; c < C; ++c) {
        ans[r] += m[c] * (*this)[r][c];
      }
    }
    return ans;
  }
  class Row {
   public:
    Row(Matrix<T> *M, size_t row) : M(M), row(row) {}
    T &operator[](size_t col) {
      if (col < 0 || col >= M->C) throw std::out_of_range("Invalid column ID");
      return M->A[row][col];
    }
    const T &operator[](size_t col) const {
      if (col < 0 || col >= M->C) throw std::out_of_range("Invalid column ID");
      return M->A[row][col];
    }

   private:
    Matrix<T> *M;
    size_t row;
  };
  Row operator[](size_t row) {
    if (row < 0 || row >= R) throw std::out_of_range("Invalid row ID");
    return Row(this, row);
  }
  const Row operator[](size_t row) const {
    if (row < 0 || row >= R) throw std::out_of_range("Invalid row ID");
    return Row(const_cast<Matrix<T> *>(this), row);
  }
  Matrix<T> transposed() const {
    Matrix<T> M(*this);
    M.transpose();
    return M;
  }
  Matrix<T> inverted() const {
    if (R != C) throw std::runtime_error("Matrix not square");
    Matrix<T> M(*this);
    M.invert();
    return M;
  }
  Matrix<T> &transpose() {
    A.resize(max(R, C));
    for (size_t i = 0; i < C; ++i) A[i].resize(max(R, C));
    for (size_t i = 0; i < R; ++i) {
      for (size_t j = i + 1; j < C; ++j) swap(A[i][j], A[j][i]);
    }
    for (size_t i = 0; i < C; ++i) A[i].resize(R);
    A.resize(C);
    return *this;
  }
  Matrix<T> &invert() {
    addColumnsRight(C, def);
    for (size_t i = 0; i < R; ++i) A[i][R + i] = 1;
    toReducedRowEchelon();
    if (!isIdentity()) throw std::runtime_error("Matrix not invertible");
    removeColumnsLeft(C / 2);
    return *this;
  }

 private:
  T toReducedRowEchelon() {
    size_t pivot = 0;
    T factor = 1;
    for (size_t i = 0; i < C && pivot < R; ++i) {
      pair<T, size_t> Q = {A[pivot][i], pivot};
      for (size_t j = pivot + 1; j < R; ++j)
        if (A[j][i] != 0) Q = {A[j][i], j};
      if (Q.first == 0) continue;
      if (Q.second != i) swap(A[Q.second], A[pivot]);
      for (size_t j = i + 1; j < C; ++j) A[pivot][j] /= A[pivot][i];
      factor /= A[pivot][i];
      A[pivot][i] = 1;
      for (size_t j = 0; j < R; ++j) {
        if (j != pivot) {
          for (size_t k = i + 1; k < C; ++k) A[j][k] -= A[pivot][k] * A[j][i];
          A[j][i] = 0;
        }
      }
      ++pivot;
    }
    return factor;
  }
  size_t R, C;
  vector<vector<T>> A;
  T def;
};
template <typename T>
std::ostream &operator<<(std::ostream &os, const Matrix<T> &m) {
  for (size_t r = 0; r < m.rows(); ++r)
    for (size_t c = 0; c < m.columns(); ++c)
      os << m[r][c] << " \n"[c == m.columns() - 1];
  return os;
}
class luckyarrays {
 public:
  void solve(istream &cin, ostream &cout) {
    int N, M;
    cin >> N >> M;
    vector2<Field<777777777>> W(3, 3);
    cin >> W;
    Matrix<Field<777777777>> Id(3, 3, 0);
    Id[0][0] = Id[1][1] = Id[2][2] = 1;
    if (N == 1) {
      for (int i = 0; i < M; ++i) {
        int j, k;
        cin >> j >> k;
        cout << (k == 0 ? 3 : 1) << '\n';
      }
      return;
    }
    vector<Matrix<Field<777777777>>> T;
    for (int i = 0; i < 4; ++i) {
      T.emplace_back(W, Field<777777777>(0));
      T[i].transpose();
      if (i != 0) {
        for (int j = 0; j < 3; ++j) {
          for (int k = 0; k < 3; ++k) {
            if (j != i - 1) T[i][j][k] = 0;
          }
        }
      }
    }
    int S = 1 << logceil(N - 1);
    vector<Matrix<Field<777777777>>> Z(2 * S, Id);
    for (int i = 1; i < N; ++i) Z[S + i - 1] = T[0];
    for (int i = S - 1; i > 0; --i) Z[i] = Z[2 * i + 1] * Z[2 * i];
    vector<int> A(N, 0);
    for (int i = 0; i < M; ++i) {
      int j, k;
      cin >> j >> k;
      --j;
      A[j] = k;
      if (j != 0) {
        int h = S + j - 1;
        Z[h] = T[k];
        h /= 2;
        while (h > 0) {
          Z[h] = Z[2 * h + 1] * Z[2 * h];
          h /= 2;
        }
      }
      vector<Field<777777777>> Q(3, 0);
      if (A[0] == 0)
        Q[0] = Q[1] = Q[2] = 1;
      else
        Q[A[0] - 1] = 1;
      Q = Z[1] * Q;
      cout << Q[0] + Q[1] + Q[2] << '\n';
    }
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  luckyarrays solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}
