Problem: Arkady wants to have a dinner. He has just returned from a shop where he has bought a semifinished cutlet. He only needs to fry it. The cutlet should be fried for 2n seconds, in particular, it should be fried for n seconds on one side and n seconds on the other side. Arkady has already got a frying pan and turn on fire, but understood that maybe he won't be able to flip the cutlet exactly after n seconds after the beginning of cooking.

Arkady is too busy with sorting sticker packs in his favorite messenger and can flip the cutlet only in some periods of time. Namely, there are k periods of time in which he can do it, the i-th of them is an interval of time from li seconds after he starts cooking till ri seconds, inclusive. Arkady decided that it's not required to flip the cutlet exactly in the middle of cooking, instead, he will flip it several times in such a way that the cutlet will be fried exactly n seconds on one side and n seconds on the other side in total.

Help Arkady and find out if it's possible for him to cook the cutlet, if he is able to flip the cutlet only in given periods of time; and if yes, find the minimum number of flips he needs to cook the cutlet.

Input

The first line contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 100) — the number of seconds the cutlet should be cooked on each side and number of periods of time in which Arkady can flip it.

The next k lines contain descriptions of these intervals. Each line contains two integers li and ri (0 ≤ li ≤ ri ≤ 2·n), meaning that Arkady can flip the cutlet in any moment starting from li seconds after the beginning of cooking and finishing at ri seconds after beginning of cooking. In particular, if li = ri then Arkady can flip the cutlet only in the moment li = ri. It's guaranteed that li > ri - 1 for all 2 ≤ i ≤ k.

Output

Output "Hungry" if Arkady won't be able to fry the cutlet for exactly n seconds on one side and exactly n seconds on the other side.

Otherwise, output "Full" in the first line, and the minimum number of times he should flip the cutlet in the second line.

Examples

Input

10 2
3 5
11 13


Output

Full
2


Input

10 3
3 5
9 10
11 13


Output

Full
1


Input

20 1
3 19


Output

Hungry

Note

In the first example Arkady should flip the cutlet in time moment 3 seconds after he starts cooking and in time moment 13 seconds after he starts cooking.

In the second example, Arkady can flip the cutlet at 10 seconds after he starts cooking.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vs = vector<string>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vpdd = vector<pdd>;
template <typename T>
void ckmin(T &a, const T &b) {
  a = min(a, b);
}
template <typename T>
void ckmax(T &a, const T &b) {
  a = max(a, b);
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
namespace __input {
template <class T1, class T2>
void re(pair<T1, T2> &p);
template <class T>
void re(vector<T> &a);
template <class T, size_t SZ>
void re(array<T, SZ> &a);
template <class T>
void re(T &x) {
  cin >> x;
}
void re(double &x) {
  string t;
  re(t);
  x = stod(t);
}
template <class Arg, class... Args>
void re(Arg &first, Args &...rest) {
  re(first);
  re(rest...);
}
template <class T1, class T2>
void re(pair<T1, T2> &p) {
  re(p.first, p.second);
}
template <class T>
void re(vector<T> &a) {
  for (int i = 0; i < int((a).size()); i++) re(a[i]);
}
template <class T, size_t SZ>
void re(array<T, SZ> &a) {
  for (int i = 0; i < SZ; i++) re(a[i]);
}
}  // namespace __input
using namespace __input;
namespace __output {
template <typename T>
struct is_outputtable {
  template <typename C>
  static constexpr decltype(declval<ostream &>() << declval<const C &>(),
                            bool())
  test(int) {
    return true;
  }
  template <typename C>
  static constexpr bool test(...) {
    return false;
  }
  static constexpr bool value = test<T>(int());
};
template <
    class T, typename V = decltype(declval<const T &>().begin()),
    typename S = typename enable_if<!is_outputtable<T>::value, bool>::type>
void pr(const T &x);
template <class T,
          typename V = decltype(declval<ostream &>() << declval<const T &>())>
void pr(const T &x) {
  cout << x;
}
template <class T1, class T2>
void pr(const pair<T1, T2> &x);
template <class Arg, class... Args>
void pr(const Arg &first, const Args &...rest) {
  pr(first);
  pr(rest...);
}
template <class T, bool pretty = true>
void prContain(const T &x) {
  if (pretty) pr("{");
  bool fst = 1;
  for (const auto &a : x) pr(!fst ? pretty ? ", " : " " : "", a), fst = 0;
  if (pretty) pr("}");
}
template <class T>
void pc(const T &x) {
  prContain<T, false>(x);
  pr("\n");
}
template <class T1, class T2>
void pr(const pair<T1, T2> &x) {
  pr("{", x.first, ", ", x.second, "}");
}
template <class T, typename V, typename S>
void pr(const T &x) {
  prContain(x);
}
void ps() { pr("\n"); }
template <class Arg>
void ps(const Arg &first) {
  pr(first);
  ps();
}
template <class Arg, class... Args>
void ps(const Arg &first, const Args &...rest) {
  pr(first, " ");
  ps(rest...);
}
}  // namespace __output
using namespace __output;
namespace __algorithm {
template <typename T>
void dedup(vector<T> &v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <typename T>
typename vector<T>::const_iterator find(const vector<T> &v, const T &x) {
  auto it = lower_bound((v).begin(), (v).end(), x);
  return it != v.end() && *it == x ? it : v.end();
}
template <typename T>
size_t index(const vector<T> &v, const T &x) {
  auto it = find(v, x);
  assert(it != v.end() && *it == x);
  return it - v.begin();
}
template <typename I>
struct _reversed_struct {
  I &v_;
  explicit _reversed_struct(I &v) : v_{v} {}
  typename I::reverse_iterator begin() const { return v_.rbegin(); }
  typename I::reverse_iterator end() const { return v_.rend(); }
};
template <typename I>
_reversed_struct<I> reversed(I &v) {
  return _reversed_struct<I>(v);
}
}  // namespace __algorithm
using namespace __algorithm;
namespace __io {
void setIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << setprecision(15);
}
}  // namespace __io
using namespace __io;
template <typename T, typename U, typename TAssociativeCombineFunction,
          typename UAssociativeCombineFunction, typename UApplicator>
struct segment_tree_lazy {
  int SZ;
  T t_identity;
  U u_identity;
  TAssociativeCombineFunction TT;
  UAssociativeCombineFunction UU;
  UApplicator UT;
  std::vector<T> data;
  std::vector<bool> has_update;
  std::vector<U> updates;
  segment_tree_lazy() {}
  segment_tree_lazy(int _SZ, T _t_identity, U _u_identity,
                    TAssociativeCombineFunction _TT,
                    UAssociativeCombineFunction _UU, UApplicator _UT)
      : SZ(_SZ),
        t_identity(_t_identity),
        u_identity(_u_identity),
        TT(_TT),
        UU(_UU),
        UT(_UT) {
    data.assign(2 * SZ, t_identity);
    has_update.assign(SZ, false);
    updates.assign(SZ, u_identity);
  }
  template <typename Function>
  void assign(Function fn) {
    for (int i = 0; i < SZ; i++) data[SZ + i] = fn(i);
    for (int i = SZ - 1; i; i--) data[i] = TT(data[2 * i], data[2 * i + 1]);
    has_update.assign(SZ, false);
    updates.assign(SZ, u_identity);
  }

 private:
  void apply_update(int i, const U &u) {
    data[i] = UT(u, data[i]);
    if (i < SZ) {
      has_update[i] = true;
      updates[i] = UU(u, updates[i]);
    }
  }
  void propagate_ancestor_updates(int i) {
    for (int ht = 31 - __builtin_clz(i); ht > 0; ht--) {
      int anc = i >> ht;
      if (has_update[anc]) {
        apply_update(2 * anc, updates[anc]);
        apply_update(2 * anc + 1, updates[anc]);
        has_update[anc] = false;
        updates[anc] = u_identity;
      }
    }
  }
  void recompute_ancestors(int i) {
    for (i /= 2; i; i /= 2)
      data[i] = UT(updates[i], TT(data[2 * i], data[2 * i + 1]));
  }
  void modify_leaf(int i, T v, bool overwrite) {
    i += SZ;
    propagate_ancestor_updates(i);
    data[i] = overwrite ? v : TT(data[i], v);
    recompute_ancestors(i);
  }

 public:
  void assign(int i, T v) { modify_leaf(i, v, true); }
  void combine_and_assign(int i, T v) { modify_leaf(i, v, false); }
  void apply_update(int first, int last, U u) {
    assert(0 <= first && last <= SZ);
    first += SZ, last += SZ;
    propagate_ancestor_updates(first);
    propagate_ancestor_updates(last - 1);
    for (int i = first, j = last; i < j; i /= 2, j /= 2) {
      if (i & 1) apply_update(i++, u);
      if (j & 1) apply_update(--j, u);
    }
    recompute_ancestors(first);
    recompute_ancestors(last - 1);
  }
  T accumulate(int first, int last) {
    assert(0 <= first && last <= SZ);
    first += SZ, last += SZ;
    propagate_ancestor_updates(first);
    propagate_ancestor_updates(last - 1);
    T left = t_identity, right = t_identity;
    for (int i = first, j = last; i < j; i /= 2, j /= 2) {
      if (i & 1) left = TT(left, data[i++]);
      if (j & 1) right = TT(data[--j], right);
    }
    return TT(left, right);
  }
  T read(int i) {
    i += SZ;
    propagate_ancestor_updates(i);
    return data[i];
  }
};
const string NO = "Hungry", YES = "Full";
const int INF = 1e9;
template <typename T, bool maximum_mode>
struct monotonic_rmq {
  deque<pair<T, int>> values;
  int current_index = 0;
  bool better(const T &a, const T &b) const { return (a < b) ^ maximum_mode; }
  int add(const T &x) {
    while (!values.empty() && !better(values.back().first, x))
      values.pop_back();
    values.emplace_back(x, current_index);
    return current_index++;
  }
  T query(int index) {
    while (values.front().second < index) values.pop_front();
    assert(!values.empty());
    return values.front().first;
  }
};
int main() {
  setIO();
  int n, k;
  re(n, k);
  const int S = 2 * n + 1;
  auto make_dp = [&]() {
    array<vi, 2> dp{vi(S, INF), vi(S, INF)};
    return dp;
  };
  auto dp = make_dp();
  dp[1][0] = 0;
  auto adv = [&](int len) {
    for (int i = S - 1; i - len >= 0; i--) dp[1][i] = dp[1][i - len];
    for (int i = 0; i < len; i++) dp[1][i] = INF;
  };
  auto update = [&](int len) {
    auto next = make_dp();
    next[0] = dp[0];
    for (int i = S - 1; i - len >= 0; i--) next[1][i] = dp[1][i - len];
    for (int b = 0; b <= 1; b++) {
      monotonic_rmq<int, false> vals;
      int removed_count = 0;
      for (int i = 0; i < S; i++) {
        vals.add(1 + dp[1 ^ b][i]);
        vals.add(2 + dp[b][i]);
        if (i - len - 1 >= 0) removed_count += 2;
        if (removed_count < vals.current_index)
          ckmin(next[b][i], vals.query(removed_count));
      }
    }
    swap(dp, next);
  };
  int t = 0;
  for (int i = 0; i < k; i++) {
    int l, r;
    re(l, r);
    adv(l - t);
    t = l;
    update(r - t);
    t = r;
  }
  adv(2 * n - t);
  int ans = min(dp[0][n], dp[1][n]);
  if (ans == INF) {
    ps(NO);
    return 0;
  }
  ps(YES);
  ps(ans);
  return 0;
}