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 JAVA):

Solution:
import java.io.*;
import java.util.*;

public class F implements Runnable{
	public static void main (String[] args) {new Thread(null, new F(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		int oo = (int)2e9;
		int n = fs.nextInt();
		int k = fs.nextInt();
		int[] dp = new int[n + 1], tdp = new int[n + 1];
		Arrays.fill(dp, oo);
		dp[0] = 0;
		while(k-->0) {
			int l = fs.nextInt(), r = fs.nextInt(), len = r - l;
			for(int i = 0; i <= n; i++) tdp[i] = dp[i];
			ArrayDeque<Integer> minQueue = new ArrayDeque<>();
			for(int i = 0; i <= n; i++) {
				push(minQueue, i, dp);
				tdp[i] = Math.min(tdp[i], best(minQueue, dp) + 2);
				if(r - i >= 0 && r - i <= n) tdp[r - i] = Math.min(tdp[r - i], best(minQueue, dp) + 1);
				pop(minQueue, i - len);
			}
			for(int i = 0; i <= n; i++) dp[i] = tdp[i];
		}
		
		if(dp[n] >= oo) out.println("Hungry");
		else out.printf("Full\n%d\n", dp[n]);

		out.close();
	}
	
	void pop(ArrayDeque<Integer> minQueue, int idx) {
		if(!minQueue.isEmpty() && minQueue.peekFirst() == idx) minQueue.pollFirst();
	}
	
	int best(ArrayDeque<Integer> minQueue, int[] dp) {
		if(minQueue.isEmpty()) return (int)2e9;
		return dp[minQueue.peekFirst()];
	}
	
	void push(ArrayDeque<Integer> minQueue, int p, int[] dp) {
		while(!minQueue.isEmpty() && dp[minQueue.getLast()] >= dp[p]) minQueue.pollLast();
		minQueue.addLast(p);
	}
	
	/*
	 * dp[i][j] means the minimum number of moves to cook the cutlet on one side
	   for j seconds after processing i intervals (do iterative space saving)
	 * The length of the interval is known and so we'll build up time j with the
	   previous length values (including j) all from the previous state. It'll take
	   an extra 2 flips to so:
	   if we know the number of flips to get the cutlet to exactly t seconds and we
	   want to get it to j seconds in the current interval being processed, then we'll
	   need to flip it after it gets to t seconds in the other interval (to prevent overcooking)
	   and then flip it again when it needs to cook in our interval to get it to the desired j.
	 * There's also a case where we can just flip it once based off of the previous states.
	   The main idea for some time j, is we want the cutlet to get to its jth second of cooking
	   during our current interval (so we can do a flip if necessary). So what happens is we take
	   the min of the dp values that are allowed in our current range and use that value to calculate
	   (right - j)'s best value by taking that minimum and I guess not flipping it and instead letting
	   it cook. Still a bit hazy but it makes sense when doing the second sample by hand (especially
	   when we update times 10 and 8).
	 * Definitely had to study someone else's solution because the editorial is very obscure and
	   doesn't actually explain the important part of the problem (how to derive the +1 and +2 jumps).
	 */

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				//                br = new BufferedReader(new FileReader("testdata.out"));
				st = new StringTokenizer("");
			} catch (Exception e){e.printStackTrace();}
		}
		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
		public int nextInt() {return Integer.parseInt(next());}
		public long nextLong() {return Long.parseLong(next());}
		public double nextDouble() {return Double.parseDouble(next());}

		public String nextLine() {
			String line = "";
			try {line = br.readLine();}
			catch (Exception e) {e.printStackTrace();}
			return line;
		}
		public Integer[] nextIntegerArray(int n) {
			Integer[] a = new Integer[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public char[] nextCharArray() {return nextLine().toCharArray();}
	}

}