Problem: Problem

Aizu decided to play a game using a prime number $ P $, a set of natural numbers $ G $, and a natural number $ A $.

First, Aizu writes $ 1 $ on the paper at hand. After that, perform the following series of operations any number of times.

* Select one element from $ G $. Let this be $ g $.
* Write a new product of the number written on the paper at hand and $ g $ on the paper.
* Erase the number originally written on the paper.



If $ A $ is equal to the number written on the paper at hand divided by $ P $, Aizu wins, otherwise he loses. Determine if Aizu can win when $ P $, $ G $, and $ A $ are given.

Constraints

The input satisfies the following conditions.

* All inputs are integers.
* $ 2 \ le P \ le 2 ^ {31} -1 $
* $ 1 \ le T, | G | \ le 10 ^ 5 $
* $ 1 \ le G_i, A \ le P-1 $
* $ G_i \ ne G_j, $ if $ i \ ne j $
* The sum of $ | G | $ in all test cases does not exceed $ 10 ^ 5 $.

Input

The input is given in the following format.


$ P $ $ T $
$ Test_1 $
$ \ vdots $
$ Test_ {T} $


The input consists of multiple test cases. First, the $ 1 $ line is given the prime number $ P $ and the number of test cases $ T $. $ P $ is common to all test cases. Each test case is given in the following $ T $ line.

Each test case is given as follows.


$ | G | $ $ G_1 $ $ \ dots $ $ G_ {| G |} $ $ A $


In each test case, the number of elements of $ G $, each element of $ G $, and $ A $ are given in order, separated by a space.

Output

For each test case, if Aizu can win, $ 1 $ will be output on one line, otherwise $ 0 $ will be output on one line.

Examples

Input

7 3
1 1 2
1 2 1
3 1 2 4 5


Output

0
1
0


Input

1000000007 8
3 2 9 7 5
3 2 9 5 1000001
3 39 1002 65537 12
2 1000000006 518012930 793649232
10 459268180 313723762 835892239 612038995 90424474 366392946 38051435 854115735 5132833 320534710 421820264
1 1 1
1 1 1000000006
1 1000000006 1


Output

0
1
1
1
0
1
0
1

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <map>
#include <utility>

std::map<intmax_t, intmax_t> factor(intmax_t n) {
  std::map<intmax_t, intmax_t> res;
  for (intmax_t i = 2; i*i <= n; ++i) {
    while (n % i == 0) {
      ++res[i];
      n /= i;
    }
  }
  if (n > 1) ++res[n];
  return res;
}

template <class Tp>
Tp modpow(Tp base, intmax_t iexp, Tp mod) {
  Tp res = 1;
  for (Tp dbl = base; iexp; iexp >>= 1) {
    if (iexp & 1) res = res * dbl % mod;
    dbl = dbl * dbl % mod;
  }
  return res;
}

template <class Tp>
Tp gcd(Tp m, Tp n) {
  while (n) std::swap(m %= n, n);
  return m;
}

template <class Tp>
Tp lcm(Tp m, Tp n) {
  return m / gcd(m, n) * n;
}

intmax_t ord(intmax_t g, intmax_t p, const std::map<intmax_t, intmax_t>& f) {
  intmax_t q = p-1;
  for (const auto& pp: f) {
    for (intmax_t i = 0; i < pp.second; ++i) {
      intmax_t e = pp.first;
      if (modpow(g, q/e, p) == 1)
        q /= e;
    }
  }
  return q;
}

int main() {
  intmax_t P;
  int T;
  scanf("%jd %d", &P, &T);

  auto f = factor(P-1);
  for (int i = 0; i < T; ++i) {
    size_t g;
    scanf("%zu", &g);

    intmax_t ords = 1;
    for (size_t j = 0; j < g; ++j) {
      intmax_t gi;
      scanf("%jd", &gi);
      ords = lcm(ords, ord(gi, P, f));
    }

    intmax_t a;
    scanf("%jd", &a);

    printf("%d\n", (ords % ord(a, P, f) == 0));
  }
}