English · Original
Chinese · Translation
Formal · Original
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 2_n_ 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 _l__i_ seconds after he starts cooking till _r__i_ 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 _l__i_ and _r__i_ (0 ≤ _l__i_ ≤ _r__i_ ≤ 2·_n_), meaning that Arkady can flip the cutlet in any moment starting from _l__i_ seconds after the beginning of cooking and finishing at _r__i_ seconds after beginning of cooking. In particular, if _l__i_ = _r__i_ then Arkady can flip the cutlet only in the moment _l__i_ = _r__i_. It's guaranteed that _l__i_ > _r__i_ - 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.
[samples]
## 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.
Arkady 想要吃晚饭。他刚从商店买回一块半成品炸肉排，现在只需要煎一下。这块肉排需要总共煎 #cf_span[2n] 秒，具体来说，每面各煎 #cf_span[n] 秒。Arkady 已经准备好煎锅并开火，但他意识到自己可能无法在烹饪开始后恰好 #cf_span[n] 秒时翻转肉排。
Arkady 正忙于在自己最喜欢的即时通讯软件中整理贴纸包，因此他只能在某些特定时间段内翻转肉排。具体来说，有 #cf_span[k] 个时间段可以进行翻转，第 #cf_span[i] 个时间段是从烹饪开始后第 #cf_span[li] 秒到第 #cf_span[ri] 秒（包含两端）。Arkady 决定不需要在烹饪中途精确翻转肉排，而是可以在这些时间段内进行多次翻转，使得肉排在两面的总煎制时间恰好各为 #cf_span[n] 秒。
请帮助 Arkady 判断他是否能在仅允许在给定时间段内翻转的前提下成功煎好肉排；如果可以，请找出他所需的最少翻转次数。
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[1 ≤ k ≤ 100]），分别表示肉排每面需要煎的秒数和允许翻转的时间段数量。
接下来的 #cf_span[k] 行描述这些时间段。每行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[0 ≤ li ≤ ri ≤ 2·n]），表示 Arkady 可以在烹饪开始后第 #cf_span[li] 秒到第 #cf_span[ri] 秒之间的任意时刻翻转肉排。特别地，若 #cf_span[li = ri]，则他只能在第 #cf_span[li] 秒这一时刻翻转。题目保证对所有 #cf_span[2 ≤ i ≤ k]，都有 #cf_span[li > ri - 1]。
如果 Arkady 无法使肉排每面恰好煎 #cf_span[n] 秒，请输出 "_Hungry_"。
否则，第一行输出 "_Full_"，第二行输出他所需的最少翻转次数。
在第一个示例中，Arkady 应该在烹饪开始后第 #cf_span[3] 秒和第 #cf_span[13] 秒翻转肉排。
在第二个示例中，Arkady 可以在烹饪开始后第 #cf_span[10] 秒翻转肉排。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[1 ≤ k ≤ 100]），分别表示肉排每面需要煎的秒数和允许翻转的时间段数量。接下来的 #cf_span[k] 行描述这些时间段。每行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[0 ≤ li ≤ ri ≤ 2·n]），表示 Arkady 可以在烹饪开始后第 #cf_span[li] 秒到第 #cf_span[ri] 秒之间的任意时刻翻转肉排。特别地，若 #cf_span[li = ri]，则他只能在第 #cf_span[li] 秒这一时刻翻转。题目保证对所有 #cf_span[2 ≤ i ≤ k]，都有 #cf_span[li > ri - 1]。
## Output
如果 Arkady 无法使肉排每面恰好煎 #cf_span[n] 秒，请输出 "_Hungry_"。否则，第一行输出 "_Full_"，第二行输出他所需的最少翻转次数。
[samples]
## Note
在第一个示例中，Arkady 应该在烹饪开始后第 #cf_span[3] 秒和第 #cf_span[13] 秒翻转肉排。在第二个示例中，Arkady 可以在烹饪开始后第 #cf_span[10] 秒翻转肉排。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the required cooking time on each side (total cooking time: $ 2n $).
Let $ k \in \mathbb{Z}^+ $ be the number of available flip intervals.
Let $ I_i = [l_i, r_i] \subseteq [0, 2n] $ for $ i \in \{1, \dots, k\} $ be the $ i $-th interval during which Arkady can flip the cutlet, with $ l_i > r_{i-1} $ for $ i \geq 2 $ (intervals are disjoint and sorted).
Let $ t_0 = 0 $, $ t_{m+1} = 2n $ be the start and end times.
Let $ t_1 < t_2 < \dots < t_m $ be flip times chosen from $ \bigcup_{i=1}^k I_i $, such that the total time on each side is exactly $ n $.
**Constraints**
1. $ 1 \leq n \leq 100{,}000 $
2. $ 1 \leq k \leq 100 $
3. $ 0 \leq l_i \leq r_i \leq 2n $ for all $ i \in \{1, \dots, k\} $
4. $ l_i > r_{i-1} $ for all $ i \in \{2, \dots, k\} $ (disjoint, non-overlapping, sorted intervals)
**Objective**
Determine if there exists a sequence of flip times $ t_1 < t_2 < \dots < t_m $ with each $ t_j \in I_{i_j} $ for some $ i_j \in \{1, \dots, k\} $, such that:
$$
\sum_{j=0}^{m} (-1)^j (t_{j+1} - t_j) = n
$$
where the left-hand side represents the total time spent on the first side (alternating sum of intervals).
Equivalently, define cumulative time on first side:
Let $ s_0 = 0 $, and for each flip at $ t_j $, the time on the first side becomes $ s_j = \sum_{i=0}^{j-1} (t_{i+1} - t_i) \cdot (-1)^i $.
We require $ s_m = n $.
Find the **minimum** number of flips $ m $ such that $ s_m = n $, or output "_Hungry_" if no such sequence exists.
API Response (JSON)
{
"problem": {
"name": "F. Cutlet",
"description": {
"content": "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 2_n_ seconds, in particular, it shoul",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF939F"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 2_n_ seconds, in particular, it shoul...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Arkady 想要吃晚饭。他刚从商店买回一块半成品炸肉排，现在只需要煎一下。这块肉排需要总共煎 #cf_span[2n] 秒，具体来说，每面各煎 #cf_span[n] 秒。Arkady 已经准备好煎锅并开火，但他意识到自己可能无法在烹饪开始后恰好 #cf_span[n] 秒时翻转肉排。\n\nArkady 正忙于在自己最喜欢的即时通讯软件中整理贴纸包，因此他只能在某些特定时间段内翻转肉排。具体来说，...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the required cooking time on each side (total cooking time: $ 2n $). \nLet $ k \\in \\mathbb{Z}^+ $ be the number of available flip intervals. \nLet $ I_i...",
"is_translate": false,
"language": "Formal"
}
]
}