#include <bits/stdc++.h>
bool RANDOM = false;
using namespace std;
double EPS = 0.0000000001;
double INF = 1000000000000000.0;
ostream_iterator<long long int> oi(cout, " ");
long long int minInt = 1;
long long int maxInt = 100;
double minDouble = -100000000000.0;
double maxDouble = 100000000000.0;
void setMaxInt(long long int newMax) { maxInt = newMax; }
void setMinInt(long long int newMin) { minInt = newMin; }
void setIntRange(long long int min, long long int max) {
  maxInt = max;
  minInt = min;
}
void setMaxDouble(double newMax) { maxDouble = newMax; }
void setMinDouble(double newMin) { minDouble = newMin; }
void setDoubleRange(double min, double max) {
  maxDouble = max;
  minDouble = min;
}
ostream& operator<<(ostream& out, pair<long long int, long long int>& c) {
  out << "<" << c.first << ", ";
  out << c.second << ">" << endl;
  return out;
}
void print() { std::cout << endl; }
template <typename A>
void print(A value) {
  std::cout << value;
}
template <typename A, typename B>
void print(A value1, B value2) {
  cout << value1 << " " << value2;
}
template <typename A, typename B, typename C>
void print(A value1, B value2, C value3) {
  cout << value1 << " " << value2 << " " << value3;
}
template <typename A, typename B, typename C, typename D>
void print(A value1, B value2, C value3, D value4) {
  cout << value1 << " " << value2 << " " << value3 << " " << value4;
}
template <typename A>
void println(A value) {
  std::cout << value << endl;
}
template <typename A, typename B>
void println(A value1, B value2) {
  cout << value1 << " " << value2 << endl;
}
template <typename A, typename B, typename C>
void println(A value1, B value2, C value3) {
  cout << value1 << " " << value2 << " " << value3 << endl;
}
template <typename A, typename B, typename C, typename D>
void println(A value1, B value2, C value3, D value4) {
  cout << value1 << " " << value2 << " " << value3 << " " << value4 << endl;
}
long long int randomint(long long int min, long long int max) {
  return rand() % (max - min + 1) + min;
}
double randomdouble(double min, double max) {
  return (rand() / (double)RAND_MAX) * (max - min) + min;
}
template <typename E>
E read() {
  E value;
  cin >> value;
  return value;
}
template <>
long long int read<long long int>() {
  if (!RANDOM) {
    long long int value;
    cin >> value;
    return value;
  } else {
    return randomint(minInt, maxInt);
  }
}
template <>
double read<double>() {
  if (!RANDOM) {
    double value;
    cin >> value;
    return value;
  } else {
    return randomdouble(minDouble, maxDouble);
  }
}
istream& operator>>(istream& in, pair<long long int, long long int>& c) {
  c.first = read<long long int>();
  c.second = read<long long int>();
  return in;
}
ostream& operator<<(ostream& out, string& c) {
  for (long long int i = 0; i < c.length(); i++) {
    putchar(c[i]);
  }
  return out;
}
template <typename E>
class Array {
 public:
  long long int size;
  Array<E>(long long int _capacity) {
    capacity = _capacity;
    array = new E[capacity];
    size = capacity;
    fill();
  }
  void sort() { std::sort(&array[0], &array[size]); }
  Array() {
    capacity = 4;
    array = new E[capacity];
    size = 0;
  }
  Array(vector<E>& vect) {
    long long int _size = vect.size();
    capacity = _size * 2;
    size = _size;
    array = new E[capacity];
    for (long long int i = 0; i < size; i++) {
      array[i] = vect[i];
    }
  }
  Array(long long int minBound, long long int maxBound, long long int _size) {
    srand(_size);
    capacity = _size * 2;
    size = _size;
    array = new E[capacity];
    for (long long int i = 0; i < size; i++) {
      array[i] = randomint(minBound, maxBound);
    }
  }
  void add(E item);
  long long int leftBinarySearch(E& item);
  long long int rightBinarySearch(E& item);
  pair<long long int, long long int> equalRange(E& item);
  bool binarySearch(E& item);
  void fill();
  E* begin();
  E* end();
  vector<E> toVector();
  void toString(ostream& stream);
  E& operator[](long long int i);
  E& index(long long int i);
  E* array;

 private:
  long long int capacity;
  void ensureCapacity(long long int cap);
};
template <typename E>
void Array<E>::ensureCapacity(long long int cap) {
  capacity = capacity * 2;
  E* newArray = new E[capacity];
  memcpy(newArray, array, sizeof(E) * size);
  delete[] array;
  array = newArray;
}
template <typename E>
void Array<E>::fill() {
  for (long long int i = 0; i < size; i++) {
    array[i] = 0;
  }
}
template <>
void Array<pair<long long int, long long int> >::fill() {
  for (long long int i = 0; i < size; i++) {
    array[i] = make_pair(0, 0);
  }
}
template <>
void Array<string>::fill() {
  for (long long int i = 0; i < size; i++) {
    array[i] = "";
  }
}
template <typename E>
void Array<E>::toString(ostream& stream) {
  long long int i = 0;
  while (i < size) {
    if (i == size - 1) {
      stream << array[i];
    } else {
      stream << array[i] << " ";
    }
    i++;
  }
  stream << endl;
}
template <typename E>
void Array<E>::add(E item) {
  if (capacity < size + 1) {
    ensureCapacity(size + 1);
  }
  array[size] = item;
  size++;
}
template <typename E>
E* Array<E>::begin() {
  return array;
}
template <typename E>
E* Array<E>::end() {
  return array + size;
}
template <typename E>
long long int Array<E>::leftBinarySearch(E& item) {
  return lower_bound(array, array + size, item) - array;
}
template <typename E>
long long int Array<E>::rightBinarySearch(E& item) {
  return upper_bound(array, array + size, item) - array;
}
template <typename E>
pair<long long int, long long int> Array<E>::equalRange(E& item) {
  pair<long long int*, long long int*> p(0, 0);
  p = equal_range(array, array + size, item);
  return make_pair(p.first - array, p.second - array);
}
template <typename E>
bool Array<E>::binarySearch(E& item) {
  return binary_search(array, array + size, item);
}
template <typename E>
vector<E> Array<E>::toVector() {
  vector<E> res = vector<E>(size);
  for (long long int i = 0; i < res.size(); i++) {
    res[i] = array[i];
  }
  return res;
}
template <typename T>
ostream& operator<<(ostream& out, Array<T>& c) {
  c.toString(out);
  return out;
}
ostream& operator<<(ostream& out,
                    Array<pair<long long int, long long int> >& c) {
  for (long long int i = 0; i < c.size; i++) {
    out << c[i];
  }
  return out;
}
template <typename T>
istream& operator>>(istream& in, Array<T>& c) {
  for (long long int i = 0; i < c.size; i++) {
    c[i] = read<T>();
  }
  return in;
}
ostream& operator<<(ostream& out, map<long long int, long long int>& c) {
  map<long long int, long long int>::iterator it = c.begin();
  while (it != c.end()) {
    pair<long long int, long long int> entry = *it;
    out << entry;
    it++;
  }
  return out;
}
Array<pair<long long int, long long int> > mapToArray(
    map<long long int, long long int>& c) {
  Array<pair<long long int, long long int> > res(c.size());
  map<long long int, long long int>::iterator it = c.begin();
  long long int i = 0;
  while (it != c.end()) {
    pair<long long int, long long int> entry = *it;
    res[i] = entry;
    i++;
    it++;
  }
  return res;
}
template <typename E>
E& Array<E>::operator[](long long int i) {
  if (i < size && i >= 0) {
    return array[i];
  } else {
    cout << "Array index out of bounds, index is " << i << ", size is " << size
         << endl;
    cout << "Array is " << endl;
    toString(cout);
    assert(0);
  }
}
template <typename E>
class Matrix {
 public:
  long long int rows;
  long long int columns;
  Array<E> array;
  E& get(long long int x, long long int y);
  void set(long long int x, long long int y, E& value);
  E& operator()(long long int x, long long int y);
  Matrix<E> transpose();
  pair<E*, E*> getRow(long long int y);
  Matrix<E>(long long int c, long long int r) {
    rows = r;
    columns = c;
    array = Array<E>(rows * columns);
    array.fill();
  }
  void swap(Matrix<E>& other) {
    std::swap(array, other.array);
    std::swap(rows, other.rows);
    std::swap(columns, other.columns);
  }
  Matrix<E>(long long int _columns, long long int _rows, long long int minBound,
            long long int maxBound) {
    rows = _rows;
    columns = _columns;
    long long int size = _rows * _columns;
    array = Array<E>(minBound, maxBound, size);
  }

 private:
};
template <typename E>
Matrix<E> Matrix<E>::transpose() {
  Matrix<long long int> b(rows, columns);
  for (long long int x = 0; x < columns; x++) {
    for (long long int y = 0; y < rows; y++) {
      b(y, x) = array.array[x + y * columns];
    }
  }
  return b;
}
template <typename E>
E& Matrix<E>::operator()(long long int x, long long int y) {
  if (x >= columns || x < 0) {
    cout << "x must be in range [0; " << columns - 1 << "], but it is " << x
         << endl;
    assert(0);
  }
  if (y >= rows || y < 0) {
    cout << "y must be in range [0; " << rows - 1 << "], but it is " << y
         << endl;
    assert(0);
  }
  return array.array[x + y * columns];
}
template <typename T>
istream& operator>>(istream& in, Matrix<T>& c) {
  for (long long int y = 0; y < c.rows; y++) {
    for (long long int x = 0; x < c.columns; x++) {
      c(x, y) = read<T>();
    }
  }
  return in;
}
template <typename E>
pair<E*, E*> Matrix<E>::getRow(long long int y) {
  E* f = array.array + y * columns;
  E* s = array.array + (y + 1) * columns;
  pair<E*, E*> p(f, s);
  return p;
}
template <typename T>
ostream& operator<<(ostream& out, Matrix<T>& c) {
  for (size_t y = 0; y < c.rows; y++) {
    for (size_t x = 0; x < c.columns; x++) {
      out << c(x, y) << " ";
    }
    out << endl;
  }
}
class Point {
 public:
  double x;
  double y;
  Point(double _x, double _y) {
    x = _x;
    y = _y;
  }
  Point() {
    x = 0;
    y = 0;
  }
};
double dist(Point& a, Point& b) {
  double dx = a.x - b.x;
  double dy = a.y - b.y;
  return sqrt(dx * dx + dy * dy);
}
bool cmp(double a, double b) {
  if (fabs(a - b) < EPS) {
    return true;
  } else {
    return false;
  }
}
class Triangle {
 public:
  Point A;
  Point B;
  Point C;
  double a;
  double b;
  double c;
  Triangle(Point _A, Point _B, Point _C) {
    A = _A;
    B = _B;
    C = _C;
    a = dist(C, B);
    b = dist(C, A);
    c = dist(A, B);
  }
  Triangle() {}
  double S() {
    return fabs((B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y));
  }
};
class Line {
 public:
  double A;
  double B;
  double C;
  double xmin;
  double xmax;
  Line(Point _A, Point _B, bool isSegment) { set(_A, _B, isSegment); }
  void set(Point _A, Point _B, bool isSegment) {
    if (isSegment) {
      xmin = min(_A.x, _B.x);
      xmax = max(_A.x, _B.x);
    } else {
      xmin = -INF;
      xmax = INF;
    }
    double k = (_B.y - _A.y) / (_B.x - _A.x);
    double b = _A.y - k * _A.x;
    A = k;
    B = -1.0;
    C = b;
  }
  void setSegment(Point _A, Point _B) { set(_A, _B, true); }
  void setLine(Point _A, Point _B) { set(_A, _B, false); }
  double getY(double x) { return A * x + C; }
  double length() {
    double x1 = xmin;
    double y1 = getY(xmin);
    double x2 = xmax;
    double y2 = getY(xmax);
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
  }
  long long int part(Point p) {
    if (fabs(A) > 100000000.0) {
      if (cmp(p.x, xmin)) {
        return 0;
      }
      if (p.x > xmin) {
        return 1;
      } else {
        return -1;
      }
    }
    if (cmp(A * p.x + B * p.y + C, 0.0)) {
      return 0;
    }
    if (A * p.x + B * p.y + C > 0) {
      return 1;
    }
    if (A * p.x + B * p.y + C < 0) {
      return -1;
    }
  }
};
istream& operator>>(istream& in, Point& c) {
  c.x = read<long long int>();
  c.y = read<long long int>();
}
ostream& operator<<(ostream& out, Point& c) {
  out << "[" << c.x << ", " << c.y << "]" << endl;
}
istream& operator>>(istream& in, Triangle& c) {
  in >> c.A;
  in >> c.B;
  in >> c.C;
}
ostream& operator<<(ostream& out, Triangle& c) {
  out << c.A;
  out << c.B;
  out << c.C;
}
istream& operator>>(istream& in, Line& c) {
  Point a;
  Point b;
  in >> a;
  in >> b;
  c.setLine(a, b);
}
ostream& operator<<(ostream& out, Line& c) {
  cout << "y = " << c.A << "*x + " << c.C;
}
long long int bpow(long long int a, long long int b) {
  if (b == 0) {
    return 1;
  } else {
    if (b % 2 == 0) {
      long long int half = bpow(a, b / 2);
      return half * half;
    } else {
      return bpow(a, b - 1) * a;
    }
  }
}
long long int fact(long long int n) {
  if (n == 1) {
    return 1;
  } else {
    return n * fact(n - 1);
  }
}
long long int gcd(long long int a, long long int b) {
  if (!b) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}
Array<pair<long long int, long long int> > factorize(long long int n) {
  Array<pair<long long int, long long int> > res;
  for (long long int i = 2; i < sqrt((double)n) + 1; i++) {
    if (n % i == 0) {
      pair<long long int, long long int> comp = make_pair(i, 1);
      n /= i;
      while (n % i == 0) {
        comp.second++;
        n /= i;
      }
      res.add(comp);
    }
  }
  if (n > 1) {
    res.add(make_pair(n, 1));
  }
  return res;
}
long long int euler(long long int n) {
  Array<pair<long long int, long long int> > fact = factorize(n);
  long long int res = 1;
  for (unsigned long long int i = 0; i < fact.size; i++) {
    long long int factor =
        pow((double)fact[i].first, (double)fact[i].second) -
        pow((double)fact[i].first, (double)fact[i].second - 1);
    res *= factor;
  }
  return res;
}
long long int inversePrime(long long int a, long long int m) {
  return bpow(a, m - 2) % m;
}
long long int inverseCoprimes(long long int a, long long int m) {
  return bpow(a, euler(m) - 1) % m;
}
long long int inverse(long long int a, long long int m) {
  if (gcd(a, m) == 1) {
    return inverseCoprimes(a, m);
  } else {
    assert(0);
    return -1;
  }
}
Array<long long int> enumerateDivisors(long long int n) {
  Array<pair<long long int, long long int> > divs = factorize(n);
  vector<long long int> totals = vector<long long int>(divs.size + 1);
  totals[0] = 1;
  for (unsigned long long int i = 1; i < divs.size + 1; i++) {
    totals[i] = totals[i - 1] * (divs[i - 1].second + 1);
  }
  Array<long long int> res;
  for (long long int i = 0; i < totals[totals.size() - 1]; i++) {
    vector<long long int> values = vector<long long int>(divs.size);
    for (unsigned long long int j = 0; j < values.size(); j++) {
      values[j] = (i / totals[j]) % (divs[j].second + 1);
    }
    long long int r = 1;
    for (unsigned long long int i = 0; i < values.size(); i++) {
      r *= bpow(divs[i].first, values[i]);
    }
    res.add(r);
  }
  return res;
}
void reverse(char* str) {
  char temp;
  size_t len = strlen(str) - 1;
  size_t i;
  size_t k = len;
  for (i = 0; i < len; i++) {
    temp = str[k];
    str[k] = str[i];
    str[i] = temp;
    k--;
    if (k == (len / 2)) {
      break;
    }
  }
}
map<long long int, long long int> count(Array<long long int> a) {
  map<long long int, long long int> res;
  for (long long int i = 0; i < a.size; i++) {
    res[a[i]]++;
  }
  return res;
}
void itoa(long long int n, char s[]) {
  long long int radix = 10;
  long long int i, sign;
  if ((sign = n) < 0) n = -n;
  i = 0;
  do {
    s[i++] = n % radix + '0';
  } while ((n /= radix) > 0);
  if (sign < 0) s[i++] = '-';
  s[i] = '\0';
  reverse(s);
}
long long int* vectorToArray(vector<long long int> v) {
  long long int* a = new long long int[v.size()];
  for (unsigned long long int i = 0; i < v.size(); i++) {
    a[i] = v[i];
  }
  return a;
}
char* stringToNumber(long long int number) {
  char* res = new char[100];
  itoa(number, res);
  return res;
}
long long int numberToString(char* str) { return atoi(str); }
long long int booleanAnswerBinarySearch(Array<long long int> params,
                                        long long int left, long long int right,
                                        bool (*f)(Array<long long int> params,
                                                  long long int v)) {
  if (f(params, left) && !f(params, left - 1)) {
    return left;
  }
  if (f(params, right) && !f(params, right + 1)) {
    return right;
  }
  long long int middle = (left + right) / 2;
  long long int g = f(params, middle);
  if (g) {
    return booleanAnswerBinarySearch(params, left, middle, f);
  } else {
    return booleanAnswerBinarySearch(params, middle + 1, right, f);
  }
}
Array<Array<long long int> > enumerarePermutations(long long int n) {
  long long int fac = fact(n);
  Array<long long int> v;
  for (long long int i = 0; i < n; i++) {
    v.add(i + 1);
  }
  Array<Array<long long int> > res;
  for (long long int i = 0; i < fac - 1; i++) {
    Array<long long int> c(n);
    copy(v.array, v.array + v.size, c.array);
    res.add(c);
    next_permutation(v.array, v.array + v.size);
  }
  Array<long long int> c(n);
  copy(v.array, v.array + v.size, c.array);
  res.add(c);
  return res;
}
template <typename T>
Array<Array<T> > enumerarePermutations(Array<T> array) {
  long long int n = array.size;
  long long int fac = fact(n);
  Array<T> v;
  for (long long int i = 0; i < n; i++) {
    v.add(array[i]);
  }
  Array<Array<T> > res;
  for (long long int i = 0; i < fac - 1; i++) {
    Array<T> c(n);
    copy(v.array, v.array + v.size, c.array);
    res.add(c);
    next_permutation(v.array, v.array + v.size);
  }
  Array<T> c(n);
  copy(v.array, v.array + v.size, c.array);
  res.add(c);
  return res;
}
Array<Array<long long int> > enumerareTuples(long long int n, long long int k) {
  long long int q = bpow(k, n);
  Array<Array<long long int> > res(q);
  for (long long int i = 0; i < q; i++) {
    Array<long long int> tuple(n);
    for (long long int j = 0; j < n; j++) {
      tuple[j] = (i / bpow(k, j)) % k;
    }
    res[i] = tuple;
  }
  return res;
}
template <typename T>
Array<Array<long long int> > enumerareTuples(long long int n, Array<T> array) {
  long long int k = array.size;
  long long int q = bpow(k, n);
  Array<Array<T> > res(q);
  for (long long int i = 0; i < q; i++) {
    Array<long long int> tuple(n);
    for (long long int j = 0; j < n; j++) {
      tuple[j] = array[(i / bpow(k, j)) % k];
    }
    res[i] = tuple;
  }
  return res;
}
bool* sieve(long long int bound) {
  bool* array = new bool[bound + 1]();
  for (long long int i = 2; i * i <= bound; i++) {
    if (!array[i]) {
      for (long long int j = i + i; j <= bound; j += i) {
        array[j] = 1;
      }
    }
  }
  return array;
}
long long int f(long long int k) { return k & (k + 1); }
string alignLeft(string a, long long int length, char ch) {
  if (a.length() < length) {
    a = string(length - a.length(), ch) + a;
  }
  return a;
}
string decToRadix(long long int n, long long int radix) {
  string res("");
  if (n == 0) {
    res.push_back('0');
    return res;
  }
  while (n) {
    long long int digit = n % radix;
    res.push_back((char)(digit + '0'));
    n /= radix;
  }
  reverse(res.begin(), res.end());
  return res;
}
long long int radixToDec(string s, long long int radix) {
  long long int res = 0;
  reverse(s.begin(), s.end());
  for (long long int i = 0; i < s.length(); i++) {
    res += (s[i] - '0') * bpow(radix, i);
  }
  return res;
}
class F {
 public:
  long long int (*f)(long long int, long long int);
  long long int (*inverse)(long long int, long long int);
  long long int NEUTRAL;
  F(long long int (*pf)(long long int, long long int),
    long long int (*pinverse)(long long int, long long int), long long int n) {
    f = pf;
    inverse = pinverse;
    NEUTRAL = n;
  }
  F() {}
  long long int operator()(long long int a, long long int b) { return f(a, b); }
  long long int inversed(long long int a, long long int b) {
    return inverse(a, b);
  }
};
class BIT {
 public:
  F f;
  Array<long long int> tree;
  Array<long long int> array;
  BIT(F func, Array<long long int> source) {
    Array<long long int> arr(source.size);
    copy(source.begin(), source.end(), arr.begin());
    array = arr;
    f = func;
    Array<long long int> tr(source.size);
    tree = tr;
    for (long long int i = 0; i < source.size; i++) {
      add(i, array[i]);
    }
  }
  void add(long long int i, long long int delta) {
    for (long long int u = i; u < tree.size; u = u | (u + 1)) {
      tree[u] = f(tree[u], delta);
    }
  }
  long long int value(long long int l, long long int r) {
    return f.inversed(p(r), p(l - 1));
  }
  long long int p(long long int v) {
    if (v < 0) {
      return 0;
    }
    if (v == 0) {
      return tree[0];
    } else {
      return f(tree[v], p((v & (v + 1)) - 1));
    }
  }
};
class Graph {
 public:
  long long int n = 0;
  long long int m = 0;
  vector<vector<long long int> > adj;
  vector<vector<long long int> > w;
  bool isDirected = false;
  bool isWeighted = false;
  Graph() {}
  void setDirected() { this->isDirected = true; }
  void setWeighted() { this->isWeighted = true; }
  Graph(long long int n) {
    this->n = n;
    vector<vector<long long int> > _adj(2 * n + 1);
    vector<vector<long long int> > _w(2 * n + 1);
    adj = _adj;
    w = _w;
  }
  void readByMatrix() {
    bool last = this->isDirected;
    this->isDirected = true;
    for (long long int i = 0; i < n; i++) {
      for (long long int j = 0; j < n; j++) {
        long long int x;
        cin >> x;
        if (this->isWeighted) {
          if (x != -1) {
            this->addWeighted(i, j, x);
          }
        } else {
          if (x != 0) {
            this->add(i, j);
          }
        }
      }
    }
    this->isDirected = last;
  }
  void printWeights() {
    for (long long int i = 0; i < n; i++) {
      cout << i << " {";
      for (long long int j = 0; j < w[i].size(); j++) {
        if (j != adj[i].size() - 1) {
          cout << w[i][j] << " ";
        } else {
          cout << w[i][j];
        }
      }
      cout << "}";
      cout << endl;
    }
  }
  void add(long long int a, long long int b) {
    this->m++;
    adj[a].push_back(b);
    if (!this->isDirected) {
      this->m++;
      adj[b].push_back(a);
    }
  }
  void addWeighted(long long int a, long long int b, long long int weight) {
    this->m++;
    adj[a].push_back(b);
    w[a].push_back(weight);
    if (!this->isDirected) {
      this->m++;
      adj[b].push_back(a);
      w[b].push_back(weight);
    }
  }
  void dfs(long long int v, long long int* p, vector<long long int>& graypath,
           Array<long long int>& cycles, Array<long long int>& res,
           Array<long long int>& outs, long long int* color) {
    color[v] = 1;
    res.add(v);
    graypath.push_back(v);
    for (long long int i = 0; i < adj[v].size(); i++) {
      long long int u = adj[v][i];
      if (color[u] == 0) {
        p[u] = v;
        dfs(u, p, graypath, cycles, res, outs, color);
      }
      if (color[u] == 1) {
        if (p[v] != u) {
          Array<long long int> cycle;
          bool now = false;
          for (long long int i = 0; i < graypath.size(); i++) {
            if (graypath[i] == u) {
              now = true;
            }
            if (now) {
              cycle.add(graypath[i]);
            }
            if (graypath[i] == v) {
              now = false;
            }
          }
          cycles = cycle;
        }
      }
    }
    graypath.pop_back();
    color[v] = 2;
    outs.add(v);
  }
  Array<long long int> dfs(long long int number) {
    long long int* color = new long long int[n]();
    long long int* p = new long long int[n]();
    Array<long long int> res;
    Array<long long int> outs;
    Array<long long int> cycles;
    vector<long long int> path;
    dfs(number, p, path, cycles, res, outs, color);
    return res;
  }
  Array<Array<long long int> > findConnectedComponents() {
    Array<Array<long long int> > res;
    long long int* array = new long long int[n]();
    for (long long int i = 0; i < n; i++) {
      if (!array[i]) {
        Array<long long int> component = dfs(i);
        for (long long int j = 0; j < component.size; j++) {
          array[component[j]] = i + 1;
        }
        res.add(component);
      }
    }
    return res;
  }
  void shortestPath(Array<long long int>& p, long long int from,
                    long long int to, Array<long long int>& res) {
    if (from == to) {
      res.add(from);
    } else {
      res.add(to);
      long long int newTo = p[to];
      shortestPath(p, from, newTo, res);
    }
  }
  Array<long long int> shortestPath(Array<long long int>& p, long long int from,
                                    long long int to) {
    Array<long long int> res;
    shortestPath(p, from, to, res);
    reverse(res.begin(), res.end());
    return res;
  }
  Array<long long int> bfsPath(long long int s, long long int t) {
    Array<long long int> p(n);
    Array<long long int> dists(n);
    bfs(p, dists, s);
    for (long long int i = 0; i < n; i++) {
      dists[i] = -1;
    }
    return shortestPath(p, s, t);
  }
  Array<long long int> bfsDists(long long int root) {
    Array<long long int> p(n);
    Array<long long int> dists(n);
    for (long long int i = 0; i < n; i++) {
      dists[i] = -1;
    }
    bfs(p, dists, root);
    return dists;
  }
  Array<long long int> findCycles() {
    long long int* color = new long long int[n]();
    long long int* p = new long long int[n]();
    Array<long long int> res;
    Array<long long int> outs;
    Array<long long int> cycles;
    vector<long long int> graypath;
    dfs(0, p, graypath, cycles, res, outs, color);
    return cycles;
  }
  void bfs(Array<long long int>& p, Array<long long int>& dists,
           long long int root) {
    queue<long long int> q;
    q.push(root);
    long long int* visited = new long long int[this->n]();
    visited[root] = true;
    dists[root] = 0;
    while (!q.empty()) {
      long long int v = q.front();
      q.pop();
      for (long long int i = 0; i < adj[v].size(); i++) {
        long long int u = adj[v][i];
        if (!visited[u]) {
          visited[u] = true;
          dists[u] = dists[v] + 1;
          p[u] = v;
          q.push(u);
        }
      }
    }
  }
  Array<long long int> toposort() {
    n++;
    vector<long long int> newAdj;
    adj[n] = newAdj;
    for (long long int i = 0; i < n - 1; i++) {
      this->add(n - 1, i);
    }
    Array<long long int> res;
    Array<long long int> outs;
    vector<long long int> path;
    Array<long long int> cycles;
    long long int* color = new long long int[n]();
    long long int* pr = new long long int[n]();
    dfs(n - 1, pr, path, cycles, res, outs, color);
    n--;
    Array<long long int> p(outs.size - 1);
    for (long long int i = 0; i < outs.size - 1; i++) {
      p[i] = outs[i];
    }
    reverse(p.begin(), p.end());
    Array<long long int> r(p.size);
    for (long long int i = 0; i < p.size; i++) {
      r[p[i]] = i;
    }
    for (long long int i = 0; i < n; i++) {
      for (long long int j = 0; j < adj[i].size(); j++) {
        long long int v = adj[i][j];
        if (r[i] >= r[v]) {
          Array<long long int> sh(0);
          return sh;
        }
      }
    }
    return p;
  }
  long long int INF = 1000000000;
  long long int INFP = 1000000000 / 2;
  void Dijkstra(Array<long long int>& p, Array<long long int>& d,
                long long int s) {
    for (long long int i = 0; i < n; i++) {
      d.add(this->INF);
    }
    d[s] = 0;
    for (long long int i = 0; i < n; i++) {
      p.add(this->INF);
    }
    p[s] = s;
    set<pair<long long int, long long int> > q;
    q.insert(make_pair(d[s], s));
    while (!q.empty()) {
      long long int v = q.begin()->second;
      q.erase(q.begin());
      for (size_t j = 0; j < adj[v].size(); ++j) {
        long long int to = adj[v][j];
        long long int len = w[v][j];
        if (d[v] + len < d[to]) {
          q.erase(make_pair(d[to], to));
          d[to] = d[v] + len;
          p[to] = v;
          q.insert(make_pair(d[to], to));
        }
      }
    }
  }
};
long long int clp2(long long int x) {
  x--;
  for (long long int p = 1; p < 32; p <<= 1) x |= (x >> p);
  return ++x;
}
void fillArray(Array<long long int>& a) {
  long long int need = clp2(a.size);
  for (long long int i = a.size; i < need; i++) {
    a.add(0);
  }
}
istream& operator>>(istream& in, Graph& g) {
  long long int n;
  long long int m;
  cin >> n >> m;
  Graph graph(n);
  graph.isDirected = g.isDirected;
  graph.isWeighted = g.isWeighted;
  for (long long int i = 0; i < m; i++) {
    long long int x;
    long long int y;
    cin >> x >> y;
    if (!graph.isWeighted) {
      graph.add(x - 1, y - 1);
    } else {
      long long int w;
      cin >> w;
      graph.addWeighted(x - 1, y - 1, w);
    }
  }
  g = graph;
  return in;
}
ostream& operator<<(ostream& out, Graph& g) {
  for (long long int i = 0; i < g.n; i++) {
    out << i << " {";
    for (long long int j = 0; j < g.adj[i].size(); j++) {
      if (j != g.adj[i].size() - 1) {
        out << g.adj[i][j] << " ";
      } else {
        out << g.adj[i][j];
      }
    }
    out << "}";
    out << endl;
  }
  return out;
}
int main(void) {
  RANDOM = 0;
  srand(time(0));
  long long int a;
  long long int b;
  cin >> a >> b;
  long long int maxCom = min(a, b);
  long long int maxRes = 0;
  for (long long int f = 0; f <= maxCom; f++) {
    long long int o1 = f;
    long long int n1 = 2 * f;
    long long int orest = a - o1;
    long long int nrest = b - n1;
    if (orest >= 0 && nrest >= 0) {
      long long int s = min(orest / 2, nrest);
      long long int total = s + f;
      if (total > maxRes) {
        maxRes = total;
      }
    }
  }
  cout << maxRes;
}
