#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-9;
const double pi = 3.14159265358979323846264338327950288419716939937510;
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int mod2 = 1000000006;
const long long infll = 0x3f3f3f3f3f3f3f3fLL;
const int dx[8] = {0, 1, 0, -1, -1, 1, 1, -1};
const int dy[8] = {1, 0, -1, 0, 1, 1, -1, -1};
template <typename T>
inline bool RD(T& v) {
  char c;
  bool n;
  while (c = getchar(), c != '-' && (c < '0' || c > '9'))
    if (c == EOF) return false;
  if (c == '-') {
    n = true;
    v = 0;
  } else {
    n = false;
    v = c - '0';
  }
  while (c = getchar(), c >= '0' && c <= '9') v = (v << 3) + (v << 1) + c - '0';
  if (n) v *= -1;
  return true;
}
template <typename T>
inline bool RD(T& a, T& b) {
  return RD(a) && RD(b);
}
template <typename T>
inline bool RD(T& a, T& b, T& c) {
  return RD(a, b) && RD(c);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d) {
  return RD(a, b, c) && RD(d);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e) {
  return RD(a, b, c, d) && RD(e);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e, T& f) {
  return RD(a, b, c, d, e) && RD(f);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e, T& f, T& g) {
  return RD(a, b, c, d, e, f) && RD(g);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h) {
  return RD(a, b, c, d, e, f, g) && RD(h);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i) {
  return RD(a, b, c, d, e, f, g, h) && RD(i);
}
template <typename T>
inline bool RD(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, T& j) {
  return RD(a, b, c, d, e, f, g, h, i) && RD(j);
}
inline int RD() {
  int v;
  RD(v);
  return v;
}
static char _BUF_[1 << 15], *_HEAD_ = _BUF_, *_TAIL_ = _BUF_;
inline static char getchar_buffered() {
  return _HEAD_ == _TAIL_ &&
                 (_TAIL_ = (_HEAD_ = _BUF_) + fread(_BUF_, 1, 1 << 15, stdin),
                  _HEAD_ == _TAIL_)
             ? EOF
             : *_HEAD_++;
}
template <typename T>
inline bool RDB(T& v) {
  char c;
  bool n;
  while (c = getchar_buffered(), c != '-' && (c < '0' || c > '9'))
    if (c == EOF) return false;
  if (c == '-') {
    n = true;
    v = 0;
  } else {
    n = false;
    v = c - '0';
  }
  while (c = getchar_buffered() - '0', c >= 0 && c <= 9)
    v = (v << 3) + (v << 1) + c;
  if (n) v *= -1;
  return true;
}
template <typename T>
inline bool RDB(T& a, T& b) {
  return RDB(a) && RDB(b);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c) {
  return RDB(a, b) && RDB(c);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d) {
  return RDB(a, b, c) && RDB(d);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e) {
  return RDB(a, b, c, d) && RDB(e);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e, T& f) {
  return RDB(a, b, c, d, e) && RDB(f);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e, T& f, T& g) {
  return RDB(a, b, c, d, e, f) && RDB(g);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h) {
  return RDB(a, b, c, d, e, f, g) && RDB(h);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i) {
  return RDB(a, b, c, d, e, f, g, h) && RDB(i);
}
template <typename T>
inline bool RDB(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, T& j) {
  return RDB(a, b, c, d, e, f, g, h, i) && RDB(j);
}
inline int RDB() {
  int v;
  RDB(v);
  return v;
}
template <typename T>
inline void _WR(T a) {
  if (a < 0) {
    putchar('-');
    a *= -1;
  }
  T t = a / 10;
  if (t) _WR(t);
  putchar(a - (t << 1) - (t << 3) + '0');
}
template <typename T>
inline void WR_(const T& a) {
  _WR(a);
  putchar(' ');
}
template <typename T>
inline void WR(const T& a) {
  _WR(a);
  putchar('\n');
}
template <typename T>
inline void _WR(const T& a, const T& b) {
  WR_(a);
  _WR(b);
}
template <typename T>
inline void WR_(const T& a, const T& b) {
  WR_(a);
  WR_(b);
}
template <typename T>
inline void WR(const T& a, const T& b) {
  WR_(a);
  WR(b);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c) {
  WR_(a, b);
  _WR(c);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c) {
  WR_(a, b);
  WR_(c);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c) {
  WR_(a, b);
  WR(c);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d) {
  WR_(a, b, c);
  _WR(d);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d) {
  WR_(a, b, c);
  WR_(d);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d) {
  WR_(a, b, c);
  WR(d);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e) {
  WR_(a, b, c, d);
  _WR(e);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e) {
  WR_(a, b, c, d);
  WR_(e);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e) {
  WR_(a, b, c, d);
  WR(e);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f) {
  WR_(a, b, c, d, e);
  _WR(f);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f) {
  WR_(a, b, c, d, e);
  WR_(f);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e,
               const T& f) {
  WR_(a, b, c, d, e);
  WR(f);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g) {
  WR_(a, b, c, d, e, f);
  _WR(g);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g) {
  WR_(a, b, c, d, e, f);
  WR_(g);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e,
               const T& f, const T& g) {
  WR_(a, b, c, d, e, f);
  WR(g);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h) {
  WR_(a, b, c, d, e, f, g);
  _WR(h);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h) {
  WR_(a, b, c, d, e, f, g);
  WR_(h);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e,
               const T& f, const T& g, const T& h) {
  WR_(a, b, c, d, e, f, g);
  WR(h);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h, const T& i) {
  WR_(a, b, c, d, e, f, g, h);
  _WR(i);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h, const T& i) {
  WR_(a, b, c, d, e, f, g, h);
  WR_(i);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e,
               const T& f, const T& g, const T& h, const T& i) {
  WR_(a, b, c, d, e, f, g, h);
  WR(i);
}
template <typename T>
inline void _WR(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h, const T& i, const T& j) {
  WR_(a, b, c, d, e, f, g, h, i);
  _WR(j);
}
template <typename T>
inline void WR_(const T& a, const T& b, const T& c, const T& d, const T& e,
                const T& f, const T& g, const T& h, const T& i, const T& j) {
  WR_(a, b, c, d, e, f, g, h, i);
  WR_(j);
}
template <typename T>
inline void WR(const T& a, const T& b, const T& c, const T& d, const T& e,
               const T& f, const T& g, const T& h, const T& i, const T& j) {
  WR_(a, b, c, d, e, f, g, h, i);
  WR(j);
}
template <typename A>
inline istream& IN(A& a) {
  return std::cin >> a;
}
template <typename A, typename B>
inline istream& IN(A& a, B& b) {
  return std::cin >> a >> b;
}
template <typename A, typename B, typename C>
inline istream& IN(A& a, B& b, C& c) {
  return std::cin >> a >> b >> c;
}
template <typename A, typename B, typename C, typename D>
inline istream& IN(A& a, B& b, C& c, D& d) {
  return std::cin >> a >> b >> c >> d;
}
template <typename A, typename B, typename C, typename D, typename E>
inline istream& IN(A& a, B& b, C& c, D& d, E& e) {
  return std::cin >> a >> b >> c >> d >> e;
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F>
inline istream& IN(A& a, B& b, C& c, D& d, E& e, F& f) {
  return std::cin >> a >> b >> c >> d >> e >> f;
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F, typename G>
inline istream& IN(A& a, B& b, C& c, D& d, E& e, F& f, G& g) {
  return std::cin >> a >> b >> c >> d >> e >> f >> g;
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F, typename G, typename H>
inline istream& IN(A& a, B& b, C& c, D& d, E& e, F& f, G& g, H& h) {
  return std::cin >> a >> b >> c >> d >> e >> f >> g >> h;
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F, typename G, typename H, typename I>
inline istream& IN(A& a, B& b, C& c, D& d, E& e, F& f, G& g, H& h, I& i) {
  return std::cin >> a >> b >> c >> d >> e >> f >> g >> h >> i;
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F, typename G, typename H, typename I, typename J>
inline istream& IN(A& a, B& b, C& c, D& d, E& e, F& f, G& g, H& h, I& i, J& j) {
  return std::cin >> a >> b >> c >> d >> e >> f >> g >> h >> i >> j;
}
inline std::ostream& OUT() { return std::cout << std::endl; }
template <typename T>
inline ostream& _OUT(const T& a) {
  return std::cout << a;
}
template <typename T>
inline ostream& OUT_(const T& a) {
  return std::cout << a << ' ';
}
template <typename T>
inline ostream& OUT(const T& a) {
  return std::cout << a << std::endl;
}
template <typename T, typename U>
inline ostream& _OUT(const T& a, const U& b) {
  return std::cout << a << " " << b;
}
template <typename T, typename U>
inline ostream& OUT_(const T& a, const U& b) {
  return std::cout << a << " " << b << " ";
}
template <typename T, typename U>
inline ostream& OUT(const T& a, const U& b) {
  return std::cout << a << " " << b << std::endl;
}
template <typename T, typename U, typename V>
inline ostream& _OUT(const T& a, const U& b, const V& c) {
  OUT_(a, b);
  return _OUT(c);
}
template <typename T, typename U, typename V>
inline ostream& OUT_(const T& a, const U& b, const V& c) {
  OUT_(a, b);
  return OUT_(c);
}
template <typename T, typename U, typename V>
inline ostream& OUT(const T& a, const U& b, const V& c) {
  OUT_(a, b);
  return OUT(c);
}
template <typename T, typename U, typename V, typename W>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d) {
  OUT_(a, b, c);
  return _OUT(d);
}
template <typename T, typename U, typename V, typename W>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d) {
  OUT_(a, b, c);
  return OUT_(d);
}
template <typename T, typename U, typename V, typename W>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d) {
  OUT_(a, b, c);
  return OUT(d);
}
template <typename T, typename U, typename V, typename W, typename X>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d,
                     const X& e) {
  OUT_(a, b, c, d);
  return _OUT(e);
}
template <typename T, typename U, typename V, typename W, typename X>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d,
                     const X& e) {
  OUT_(a, b, c, d);
  return OUT_(e);
}
template <typename T, typename U, typename V, typename W, typename X>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d,
                    const X& e) {
  OUT_(a, b, c, d);
  return OUT(e);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f) {
  OUT_(a, b, c, d, e);
  return _OUT(f);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f) {
  OUT_(a, b, c, d, e);
  return OUT_(f);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                    const Y& f) {
  OUT_(a, b, c, d, e);
  return OUT(f);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g) {
  OUT_(a, b, c, d, e, f);
  return _OUT(g);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g) {
  OUT_(a, b, c, d, e, f);
  return OUT_(g);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                    const Y& f, const Z& g) {
  OUT_(a, b, c, d, e, f);
  return OUT(g);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h) {
  OUT_(a, b, c, d, e, f, g);
  return _OUT(h);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h) {
  OUT_(a, b, c, d, e, f, g);
  return OUT_(h);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                    const Y& f, const Z& g, const A& h) {
  OUT_(a, b, c, d, e, f, g);
  return OUT(h);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h, const B& i) {
  OUT_(a, b, c, d, e, f, g, h);
  return _OUT(i);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h, const B& i) {
  OUT_(a, b, c, d, e, f, g, h);
  return OUT_(i);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                    const Y& f, const Z& g, const A& h, const B& i) {
  OUT_(a, b, c, d, e, f, g, h);
  return OUT(i);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B, typename C>
inline ostream& _OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h, const B& i,
                     const C& j) {
  OUT_(a, b, c, d, e, f, g, h, i);
  return _OUT(j);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B, typename C>
inline ostream& OUT_(const T& a, const U& b, const V& c, const W& d, const X& e,
                     const Y& f, const Z& g, const A& h, const B& i,
                     const C& j) {
  OUT_(a, b, c, d, e, f, g, h, i);
  return OUT_(j);
}
template <typename T, typename U, typename V, typename W, typename X,
          typename Y, typename Z, typename A, typename B, typename C>
inline ostream& OUT(const T& a, const U& b, const V& c, const W& d, const X& e,
                    const Y& f, const Z& g, const A& h, const B& i,
                    const C& j) {
  OUT_(a, b, c, d, e, f, g, h, i);
  return OUT(j);
}
template <typename A>
inline void clr(A& a) {
  a.clear();
}
template <typename A, typename B>
inline void clr(A& a, B& b) {
  a.clear();
  b.clear();
}
template <typename A, typename B, typename C>
inline void clr(A& a, B& b, C& c) {
  a.clear();
  b.clear();
  c.clear();
}
template <typename A, typename B, typename C, typename D>
inline void clr(A& a, B& b, C& c, D& d) {
  a.clear();
  b.clear();
  c.clear();
  d.clear();
}
template <typename A, typename B, typename C, typename D, typename E>
inline void clr(A& a, B& b, C& c, D& d, E& e) {
  a.clear();
  b.clear();
  c.clear();
  d.clear();
  e.clear();
}
template <typename A, typename B, typename C, typename D, typename E,
          typename F>
inline void clr(A& a, B& b, C& c, D& d, E& e, F& f) {
  a.clear();
  b.clear();
  c.clear();
  d.clear();
  e.clear();
  f.clear();
}
inline long long madd(long long a, long long b,
                      const long long mod = 1000000007) {
  long long ret = (a + b) % mod;
  if (ret < 0) ret += mod;
  return ret;
}
inline long long msub(long long a, long long b,
                      const long long mod = 1000000007) {
  long long ret = (a - b) % mod;
  if (ret < 0) ret += mod;
  return ret;
}
inline long long mmul(long long a, long long b,
                      const long long mod = 1000000007) {
  return a * b % mod;
}
inline long long mpow(long long x, long long k,
                      const long long mod = 1000000007) {
  x %= mod;
  long long ret = 1;
  while (k > 0) {
    if (k & 1) ret = ret * x % mod;
    x = x * x % mod;
    k >>= 1;
  }
  return ret;
}
template <typename T, typename U>
inline bool cmax(T& a, const U& b) {
  return a < b ? a = b, true : false;
}
template <typename T, typename U>
inline bool cmin(T& a, const U& b) {
  return a > b ? a = b, true : false;
}
template <typename T, typename U>
inline T cadd(T& a, const U& b, const int mod = 1000000007) {
  a = (a * 1LL + b) % mod;
  if (a < 0) a += mod;
  return a;
}
template <typename T, typename U>
inline T csub(T& a, const U& b, const int mod = 1000000007) {
  a = (a * 1LL - b) % mod;
  if (a < 0) a += mod;
  return a;
}
template <typename T, typename U>
inline T cmul(T& a, const U& b, const int mod = 1000000007) {
  return a = (a * 1LL * b) % mod;
}
inline long long cpow(long long& x, long long k,
                      const long long mod = 1000000007) {
  x %= mod;
  long long ret = 1;
  while (k > 0) {
    if (k & 1) ret = ret * x % mod;
    x = x * x % mod;
    k >>= 1;
  }
  return x = ret;
}
template <typename T>
inline T clow(T& a, const int mod = 1000000007) {
  while (a < 0) a += mod;
  return a;
}
template <typename T>
inline T cup(T& a, const int mod = 1000000007) {
  while (a >= mod) a -= mod;
  return a;
}
template <typename T>
inline T cboth(T& a, const int mod = 1000000007) {
  while (a < 0) a += mod;
  while (a >= mod) a -= mod;
  return a;
}
template <typename T>
inline T vlow(T a, const int mod = 1000000007) {
  while (a < 0) a += mod;
  return a;
}
template <typename T>
inline T vup(T a, const int mod = 1000000007) {
  while (a >= mod) a -= mod;
  return a;
}
template <typename T>
inline T vboth(T a, const int mod = 1000000007) {
  while (a < 0) a += mod;
  while (a >= mod) a -= mod;
  return a;
}
template <typename T>
inline T max(const T& a, const T& b, const T& c) {
  return std::max(std::max(a, b), c);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d) {
  return std::max(max(a, b, c), d);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e) {
  return std::max(max(a, b, c, d), e);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f) {
  return std::max(max(a, b, c, d, e), f);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g) {
  return std::max(max(a, b, c, d, e, f), g);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h) {
  return std::max(max(a, b, c, d, e, f, g), h);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h, const T& i) {
  return std::max(max(a, b, c, d, e, f, g, h), i);
}
template <typename T>
inline T max(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h, const T& i, const T& j) {
  return std::max(max(a, b, c, d, e, f, g, h, i), j);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c) {
  return std::min(std::min(a, b), c);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d) {
  return std::min(min(a, b, c), d);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e) {
  return std::min(min(a, b, c, d), e);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f) {
  return std::min(min(a, b, c, d, e), f);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g) {
  return std::min(min(a, b, c, d, e, f), g);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h) {
  return std::min(min(a, b, c, d, e, f, g), h);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h, const T& i) {
  return std::min(min(a, b, c, d, e, f, g, h), i);
}
template <typename T>
inline T min(const T& a, const T& b, const T& c, const T& d, const T& e,
             const T& f, const T& g, const T& h, const T& i, const T& j) {
  return std::min(min(a, b, c, d, e, f, g, h, i), j);
}
inline int _1(int i) {
  assert(i < 32);
  return 1 << i;
}
inline int _7(int i) {
  assert(i < 32);
  return (1 << i) - 1;
}
inline long long _1L(int i) {
  assert(i < 64);
  return 1LL << i;
}
inline long long _7L(int i) {
  assert(i < 64);
  return (1LL << i) - 1;
}
template <typename T>
inline int i_1(T x) {
  assert((x & x - 1) == 0);
  int ret = 0;
  for (int i = sizeof(T) << 2; i; i >>= 1)
    if (x >> i) {
      ret += i;
      x >>= i;
    }
  return ret;
}
template <typename T>
inline T lowbit(T x) {
  return x & -x;
}
template <typename T>
inline bool testbit(T x, int i) {
  return (bool)(x & (T(1) << i));
}
template <typename T>
inline bool setbit(T& x, int i) {
  return (x & (T(1) << i)) ? false : (x |= (T(1) << i), true);
}
template <typename T>
inline bool resetbit(T& x, int i) {
  return (x & (T(1) << i)) ? (x &= ~(T(1) << i), true) : false;
}
template <typename T>
inline int cntbit(T x) {
  int len = sizeof(T) << 3;
  x = ((x & 0xaaaaaaaaaaaaaaaa) >> 1) + (x & 0x5555555555555555);
  x = ((x & 0xcccccccccccccccc) >> 2) + (x & 0x3333333333333333);
  x = ((x & 0xf0f0f0f0f0f0f0f0) >> 4) + (x & 0x0f0f0f0f0f0f0f0f);
  if (len >= 16) x = ((x & 0xff00ff00ff00ff00) >> 8) + (x & 0x00ff00ff00ff00ff);
  if (len >= 32)
    x = ((x & 0xffff0000ffff0000) >> 16) + (x & 0x0000ffff0000ffff);
  if (len >= 64)
    x = ((x & 0xffffffff00000000) >> 32) + (x & 0x00000000ffffffff);
  return x;
}
template <typename T>
inline T reversebit(T x) {
  int len = sizeof(T) << 3;
  x = ((x & 0xaaaaaaaaaaaaaaaa) >> 1) | ((x & 0x5555555555555555) << 1);
  x = ((x & 0xcccccccccccccccc) >> 2) | ((x & 0x3333333333333333) << 2);
  x = ((x & 0xf0f0f0f0f0f0f0f0) >> 4) | ((x & 0x0f0f0f0f0f0f0f0f) << 4);
  if (len >= 16)
    x = ((x & 0xff00ff00ff00ff00) >> 8) | ((x & 0x00ff00ff00ff00ff) << 8);
  if (len >= 32)
    x = ((x & 0xffff0000ffff0000) >> 16) | ((x & 0x0000ffff0000ffff) << 16);
  if (len >= 64)
    x = ((x & 0xffffffff00000000) >> 32) | ((x & 0x00000000ffffffff) << 32);
  return x;
}
inline int cntbit(int x) {
  x = ((x & 0xaaaaaaaa) >> 1) + (x & 0x55555555);
  x = ((x & 0xcccccccc) >> 2) + (x & 0x33333333);
  x = ((x & 0xf0f0f0f0) >> 4) + (x & 0x0f0f0f0f);
  x = ((x & 0xff00ff00) >> 8) + (x & 0x00ff00ff);
  x = ((x & 0xffff0000) >> 16) + (x & 0x0000ffff);
  return x;
}
inline int cntbit(long long x) {
  x = ((x & 0xaaaaaaaaaaaaaaaa) >> 1) + (x & 0x5555555555555555);
  x = ((x & 0xcccccccccccccccc) >> 2) + (x & 0x3333333333333333);
  x = ((x & 0xf0f0f0f0f0f0f0f0) >> 4) + (x & 0x0f0f0f0f0f0f0f0f);
  x = ((x & 0xff00ff00ff00ff00) >> 8) + (x & 0x00ff00ff00ff00ff);
  x = ((x & 0xffff0000ffff0000) >> 16) + (x & 0x0000ffff0000ffff);
  x = ((x & 0xffffffff00000000) >> 32) + (x & 0x00000000ffffffff);
  return int(x);
}
inline int reversebit(int x) {
  x = ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1);
  x = ((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2);
  x = ((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4);
  x = ((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8);
  x = ((x & 0xffff0000) >> 16) | ((x & 0x0000ffff) << 16);
  return x;
}
inline long long reversebit(long long x) {
  x = ((x & 0xaaaaaaaaaaaaaaaa) >> 1) | ((x & 0x5555555555555555) << 1);
  x = ((x & 0xcccccccccccccccc) >> 2) | ((x & 0x3333333333333333) << 2);
  x = ((x & 0xf0f0f0f0f0f0f0f0) >> 4) | ((x & 0x0f0f0f0f0f0f0f0f) << 4);
  x = ((x & 0xff00ff00ff00ff00) >> 8) | ((x & 0x00ff00ff00ff00ff) << 8);
  x = ((x & 0xffff0000ffff0000) >> 16) | ((x & 0x0000ffff0000ffff) << 16);
  x = ((x & 0xffffffff00000000) >> 32) | ((x & 0x00000000ffffffff) << 32);
  return x;
}
template <typename T>
inline T gcd(T a, T b) {
  while (b != 0) {
    T tmp = b;
    b = a % b;
    a = tmp;
  }
  return a;
}
template <typename T>
inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
inline long long minv(long long x, const long long mod = 1000000007) {
  return mpow(x, mod - 2, mod);
}
const int _ = (int)(1e3 + 10);
const int __ = (int)(1e6 + 10);
const int LOG = 18;
int n, k;
struct Point {
  int x, y;
  void read() { RDB(x, y); }
};
Point stones[7];
Point monsters[_];
bool vis[_];
vector<pair<long long, long long> >* shoot[7][_];
int shoot_order[7][_];
map<pair<int, int>, vector<pair<long long, long long> > > lines[7];
bool dfs2(vector<int> mids, int used, int rest) {
  if (mids.empty()) return true;
  if (mids.size() > rest) return false;
  for (int mid : mids) {
    for (long long i = 0; i < (long long)(k); ++i)
      if (!testbit(used, i)) {
        int order = shoot_order[i][mid];
        set<int> s((mids).begin(), (mids).end());
        s.erase(mid);
        vis[mid] = true;
        for (long long j = 0; j < (long long)(order); ++j) {
          int t = (*shoot[i][mid])[j].second;
          if (vis[t]) goto end;
          s.insert(t);
        }
        if (dfs2(vector<int>((s).begin(), (s).end()), used | _1(i), rest - 1))
          return true;
      end:;
        vis[mid] = false;
      }
  }
  return false;
}
bool dfs(int mid, int used = 0, int rest = k) {
  for (long long i = 0; i < (long long)(k); ++i)
    if (!testbit(used, i)) {
      int order = shoot_order[i][mid];
      if (order == 0) return true;
      if (order >= rest) continue;
      vis[mid] = true;
      vector<int> t;
      for (long long j = 0; j < (long long)(order); ++j)
        t.push_back((*shoot[i][mid])[j].second);
      if (dfs2(t, used | _1(i), rest - 1)) return true;
      vis[mid] = false;
    }
  return false;
}
inline void _main() {
  RDB(k, n);
  for (long long i = 0; i < (long long)(k); ++i) stones[i].read();
  for (long long i = 0; i < (long long)(n); ++i) monsters[i].read();
  for (long long i = 0; i < (long long)(k); ++i) {
    for (long long j = 0; j < (long long)(n); ++j) {
      int dx = monsters[j].x - stones[i].x;
      int dy = monsters[j].y - stones[i].y;
      long long d = 1LL * dx * dx + 1LL * dy * dy;
      int g = gcd(abs(dx), abs(dy));
      dx /= g, dy /= g;
      lines[i][make_pair(dx, dy)].push_back(make_pair(d, j));
    }
    for (auto& x : lines[i]) {
      vector<pair<long long, long long> >& shoot_sequence = x.second;
      sort((shoot_sequence).begin(), (shoot_sequence).end());
      for (long long j = (long long)(0);
           j < (long long)(((int)(shoot_sequence).size())); ++j) {
        int m = shoot_sequence[j].second;
        shoot[i][m] = &shoot_sequence;
        shoot_order[i][m] = j;
      }
    }
  }
  int ret = 0;
  for (long long i = 0; i < (long long)(n); ++i) {
    memset((vis), (0), sizeof(vis));
    if (dfs(i, 0, k)) ++ret;
  }
  WR(ret);
}
void generate_test_case() { exit(0); }
int main() {
  _main();
  return 0;
}
