{"raw_statement":[{"iden":"statement","content":"Throughout Igor K.'s life he has had many situations worthy of attention. We remember the story with the virus, the story of his mathematical career and of course, his famous programming achievements. However, one does not always adopt new hobbies, one can quit something as well.\n\nThis time Igor K. got disappointed in one of his hobbies: editing and voicing videos. Moreover, he got disappointed in it so much, that he decided to destroy his secret archive for good.\n\nIgor K. use Pindows XR operation system which represents files and folders by small icons. At that, _m_ icons can fit in a horizontal row in any window.\n\nIgor K.'s computer contains _n_ folders in the D: disk's root catalog. The folders are numbered from 1 to _n_ in the order from the left to the right and from top to bottom (see the images). At that the folders with secret videos have numbers from _a_ to _b_ inclusive. Igor K. wants to delete them forever, at that making as few frame selections as possible, and then pressing Shift+Delete exactly once. What is the minimum number of times Igor K. will have to select the folder in order to select folders from _a_ to _b_ and only them? Let us note that if some selected folder is selected repeatedly, then it is deselected. Each selection possesses the shape of some rectangle with sides parallel to the screen's borders."},{"iden":"input","content":"The only line contains four integers _n_, _m_, _a_, _b_ (1 ≤ _n_, _m_ ≤ 109, 1 ≤ _a_ ≤ _b_ ≤ _n_). They are the number of folders in Igor K.'s computer, the width of a window and the numbers of the first and the last folders that need to be deleted."},{"iden":"output","content":"Print a single number: the least possible number of times Igor K. will have to select the folders using frames to select only the folders with numbers from _a_ to _b_."},{"iden":"examples","content":"Input\n\n11 4 3 9\n\nOutput\n\n3\n\nInput\n\n20 5 2 20\n\nOutput\n\n2"},{"iden":"note","content":"The images below illustrate statement tests.\n\nThe first test:\n\n![image](https://espresso.codeforces.com/4cf387edb795a636603e2e49bfbcaadb4774ffdc.png)\n\nIn this test we can select folders 3 and 4 with out first selection, folders 5, 6, 7, 8 with our second selection and folder 9 with our third, last selection.\n\nThe second test:\n\n![image](https://espresso.codeforces.com/5b127f6da5847287832ba9301652cd63f39a4968.png)\n\nIn this test we can first select all folders in the first row (2, 3, 4, 5), then — all other ones."}],"translated_statement":[{"iden":"statement","content":"在 Igor K. 的一生中，他经历过许多值得关注的事件。我们记得那个关于病毒的故事、他的数学生涯，当然还有他著名的编程成就。然而，人并不总是在尝试新爱好，有时也需要放弃某些东西。\n\n这一次，Igor K. 对他的一项爱好感到失望：编辑和配音视频。而且他失望到足以决定永久销毁他的秘密档案。\n\nIgor K. 使用 Pindows XR 操作系统，该系统用小图标表示文件和文件夹。在任何窗口中，一行最多可容纳 #cf_span[m] 个图标。\n\nIgor K. 的计算机 D: 盘根目录下有 #cf_span[n] 个文件夹，这些文件夹从左到右、从上到下依次编号为 #cf_span[1] 到 #cf_span[n]（见图示）。其中，包含秘密视频的文件夹编号为从 #cf_span[a] 到 #cf_span[b]（含端点）。Igor K. 希望永久删除它们，且希望尽可能减少框选次数，然后仅按一次 Shift+Delete。请问，Igor K. 最少需要多少次框选，才能恰好选中编号从 #cf_span[a] 到 #cf_span[b] 的所有文件夹，且仅选中它们？注意，如果某个文件夹被重复选中，则会被取消选中。每次框选的形状都是一个边与屏幕边平行的矩形。\n\n仅一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[a], #cf_span[b]（#cf_span[1 ≤ n, m ≤ 109]，#cf_span[1 ≤ a ≤ b ≤ n]），分别表示 Igor K. 计算机中的文件夹总数、窗口宽度，以及需要删除的第一个和最后一个文件夹的编号。\n\n输出一个整数：Igor K. 最少需要多少次使用矩形框选，才能恰好选中编号从 #cf_span[a] 到 #cf_span[b] 的所有文件夹。\n\n下图展示了题目测试用例的示意图。\n\n第一个测试用例：\n\n\n\n在本测试中，我们第一次选中文件夹 3 和 4，第二次选中文件夹 5、6、7、8，第三次选中文件夹 9。\n\n第二个测试用例：\n\n\n\n在本测试中，我们首先选中第一行的所有文件夹（2, 3, 4, 5），然后选中其余所有文件夹。"},{"iden":"input","content":"仅一行包含四个整数 #cf_span[n], #cf_span[m], #cf_span[a], #cf_span[b]（#cf_span[1 ≤ n, m ≤ 109]，#cf_span[1 ≤ a ≤ b ≤ n]），分别表示 Igor K. 计算机中的文件夹总数、窗口宽度，以及需要删除的第一个和最后一个文件夹的编号。"},{"iden":"output","content":"输出一个整数：Igor K. 最少需要多少次使用矩形框选，才能恰好选中编号从 #cf_span[a] 到 #cf_span[b] 的所有文件夹。"},{"iden":"examples","content":"输入11 4 3 9输出3输入20 5 2 20输出2"},{"iden":"note","content":"下图展示了题目测试用例的示意图。\n\n第一个测试用例：\n\n在本测试中，我们第一次选中文件夹 3 和 4，第二次选中文件夹 5、6、7、8，第三次选中文件夹 9。\n\n第二个测试用例：\n\n在本测试中，我们首先选中第一行的所有文件夹（2, 3, 4, 5），然后选中其余所有文件夹。"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n $, $ m $, $ a $, $ b $ be given integers with $ 1 \\leq n, m \\leq 10^9 $ and $ 1 \\leq a \\leq b \\leq n $.\n\nThe folders are arranged in row-major order in a grid with width $ m $, i.e., folder $ i $ is located at row $ r_i = \\left\\lfloor \\frac{i-1}{m} \\right\\rfloor $ and column $ c_i = (i-1) \\bmod m $.\n\nWe wish to select the contiguous set of folders $ \\{a, a+1, \\dots, b\\} $ using the minimum number of axis-aligned rectangular selections, where each selection toggles the state of all folders in the rectangle (selected → deselected, deselected → selected), and the goal is to have **exactly** the folders from $ a $ to $ b $ selected at the end.\n\nWe define:\n\n- Let $ r_a = \\left\\lfloor \\frac{a-1}{m} \\right\\rfloor $, $ c_a = (a-1) \\bmod m $\n- Let $ r_b = \\left\\lfloor \\frac{b-1}{m} \\right\\rfloor $, $ c_b = (b-1) \\bmod m $\n\nWe consider cases based on the vertical span of the target range:\n\n---\n\n**Case 1: All folders lie in a single row**  \nIf $ r_a = r_b $, then the entire range lies in one row.  \n→ We can select the contiguous segment from $ a $ to $ b $ in **one** rectangle.  \n**Answer: 1**\n\n---\n\n**Case 2: Folders span multiple rows**\n\nWe analyze the structure:\n\n- The target set spans rows $ r_a $ to $ r_b $.\n- We can cover:\n  1. The **partial row** at the top: from $ a $ to the end of row $ r_a $: $ [a, (r_a + 1) \\cdot m] $\n  2. The **full rows** in between: rows $ r_a + 1 $ to $ r_b - 1 $: each can be selected with one rectangle\n  3. The **partial row** at the bottom: from the start of row $ r_b $ to $ b $: $ [r_b \\cdot m + 1, b] $\n\nBut we are allowed to use **any** rectangular selections, not just aligned to the grid. However, since we must select **only** the folders from $ a $ to $ b $, and toggling a rectangle toggles all folders in it, we must avoid selecting any folder outside $[a, b]$.\n\nThus, we consider **optimal rectangular selections** that may combine partial rows.\n\nWe can always select the entire block from $ a $ to $ b $ as one rectangle if it is contiguous in the grid — but it is **not** contiguous if it spans multiple rows and the start and end are not aligned to the grid boundaries.\n\nHowever, note that the folders are arranged in row-major order, so the set $ \\{a, a+1, \\dots, b\\} $ is a **contiguous sequence in linear indexing**, but **not necessarily** a rectangle in 2D grid unless it fills complete rows or is confined to one row.\n\nBut crucially: **any contiguous segment in row-major order can be covered by at most 3 rectangles**:\n\n- One for the first (possibly partial) row,\n- One for each full row in between (each full row can be selected as one rectangle),\n- One for the last (possibly partial) row.\n\nBut we can do better: **if the entire range spans more than one row, we can always cover it with at most 3 rectangles**, and sometimes less.\n\nHowever, we can also sometimes cover multiple full rows with **one** rectangle if they are aligned — but since the selection must be a rectangle with sides parallel to the axes, and the target set is a contiguous segment in row-major order, the **only way** to cover multiple full rows is to select the entire width of those rows.\n\nBut if we select a rectangle covering multiple full rows, we will also select all columns in those rows — which may include folders **outside** $[a,b]$ if the target does not span the entire width.\n\nThus, to **avoid selecting any folder outside $[a,b]$**, we **cannot** select a full row unless the entire row is within $[a,b]$.\n\nTherefore:\n\n- If the target range starts in the middle of a row and ends in the middle of another, and spans $ k $ full rows in between, then:\n  - We need 1 rectangle for the first partial row (from $ a $ to end of row $ r_a $),\n  - We need 1 rectangle for each full row that is **completely contained** in $[a,b]$,\n  - We need 1 rectangle for the last partial row (from start of row $ r_b $ to $ b $).\n\nBut here’s the key insight:\n\n> **The minimal number of rectangular selections needed to select exactly the contiguous interval $[a,b]$ in row-major layout is:**\n>\n> $$\n> \\boxed{\n> \\begin{cases}\n> 1 & \\text{if } r_a = r_b \\\\\n> 2 & \\text{if } c_a = 0 \\text{ and } c_b = m - 1 \\\\\n> 3 & \\text{otherwise}\n> \\end{cases}\n> }\n> $$\n\n### Explanation:\n\n- **Case 1: $ r_a = r_b $**: All in one row → 1 rectangle.\n\n- **Case 2: $ c_a = 0 $ and $ c_b = m - 1 $**: The range starts at the beginning of a row and ends at the end of a row → the entire block from row $ r_a $ to $ r_b $ is a solid rectangle → 1 rectangle.\n\nWait — that contradicts the earlier logic. But if $ c_a = 0 $, then $ a = r_a \\cdot m + 1 $, and $ c_b = m - 1 $ implies $ b = (r_b + 1) \\cdot m $. So the entire block from row $ r_a $ to $ r_b $ is selected, and it's a perfect rectangle → **1 selection**.\n\nBut the problem says: we must select **only** folders from $ a $ to $ b $. So if the entire block from $ a $ to $ b $ forms a solid rectangle (i.e., starts at column 0 and ends at column $ m-1 $), then we can select it in **one** rectangle.\n\nSo correction:\n\nWe need to check if the entire range $[a,b]$ forms a **perfect rectangle** in the grid.\n\nThat happens **iff**:\n\n- $ a $ is the first element of its row: $ (a - 1) \\bmod m = 0 $\n- $ b $ is the last element of its row: $ (b - 1) \\bmod m = m - 1 $\n\nThen we can select the entire block from row $ r_a $ to $ r_b $ as **one** rectangle.\n\nOtherwise, we have:\n\n- The top partial row: must be selected separately\n- The bottom partial row: must be selected separately\n- The full rows in between: each full row can be selected as one rectangle — but we can combine **all full rows in between** into **one** rectangle? No — because if we select a rectangle covering multiple full rows, it will span the full width $ m $, and if the top and bottom are partial, then the full rows are **fully contained** in $[a,b]$, so selecting a rectangle from row $ r_a + 1 $ to $ r_b - 1 $ and column 0 to $ m-1 $ is safe — because those rows are entirely within $[a,b]$.\n\nSo if there are $ k $ full rows between $ r_a $ and $ r_b $, we can select them all in **one** rectangle.\n\nThus, the minimal number of selections is:\n\n- 1 if the entire range is a solid rectangle (i.e., $ c_a = 0 $ and $ c_b = m - 1 $)\n- 2 if either:\n  - $ c_a = 0 $ (start at row boundary) → then we can select the full rows + bottom partial row in one rectangle, and the top row is already aligned → so 2 rectangles: one for full block from row $ r_a $ to $ r_b - 1 $, and one for bottom partial row? Wait, no.\n\nLet’s restructure properly.\n\n### Final Correct Analysis:\n\nLet:\n\n- $ r_a = \\left\\lfloor \\frac{a-1}{m} \\right\\rfloor $, $ c_a = (a-1) \\bmod m $\n- $ r_b = \\left\\lfloor \\frac{b-1}{m} \\right\\rfloor $, $ c_b = (b-1) \\bmod m $\n\nWe have three segments:\n\n1. **Top partial row**: from $ a $ to end of row $ r_a $ → length $ m - c_a $\n2. **Middle full rows**: from row $ r_a + 1 $ to $ r_b - 1 $ → number of rows: $ \\max(0, r_b - r_a - 1) $\n3. **Bottom partial row**: from start of row $ r_b $ to $ b $ → length $ c_b + 1 $\n\nWe can select:\n\n- The top partial row with **one** rectangle.\n- Each full row with **one** rectangle → but we can select **all full rows together** as one rectangle (since they are contiguous vertically and span full width, and are entirely within $[a,b]$).\n- The bottom partial row with **one** rectangle.\n\nSo total: **1 (top) + 1 (middle) + 1 (bottom) = 3**\n\nBut we can sometimes reduce:\n\n- If the top partial row is actually a full row → $ c_a = 0 $, then the top row is fully included → we don’t need a separate top rectangle if we can combine it with the middle.\n\nSimilarly, if $ c_b = m - 1 $, the bottom row is full.\n\nSo:\n\n- If $ c_a = 0 $ and $ c_b = m - 1 $: entire range is a solid rectangle → **1 selection**\n- Else if $ c_a = 0 $: then top row is full → we can select from row $ r_a $ to $ r_b - 1 $ as one rectangle (covering full rows including top), and bottom partial row as one → **2 selections**\n- Else if $ c_b = m - 1 $: bottom row is full → select top partial + full rows together as one rectangle, and bottom full row is included → **2 selections**\n- Else: top and bottom are partial → need 3 selections\n\nWait — but if $ c_a = 0 $, then $ a $ is the first element of row $ r_a $. Then the entire row $ r_a $ is in $[a,b]$. Similarly, if $ c_b = m-1 $, then row $ r_b $ is entirely in $[a,b]$.\n\nSo:\n\n- If both $ c_a = 0 $ and $ c_b = m - 1 $: entire range is a rectangle → **1**\n- Else if exactly one of $ c_a = 0 $ or $ c_b = m - 1 $: then we can cover all full rows (including the one that’s fully included) with one rectangle, and the other end (partial) with one → **2**\n- Else: both ends are partial → **3**\n\nBut what if there are **no full rows in between**? For example, $ r_b = r_a + 1 $, $ c_a > 0 $, $ c_b < m - 1 $. Then we have two partial rows → need 2 selections.\n\nSo the condition is:\n\n- If $ r_a = r_b $: **1**\n- Else if $ c_a = 0 $ and $ c_b = m - 1 $: **1**\n- Else if $ c_a = 0 $ or $ c_b = m - 1 $: **2**\n- Else: **3**\n\nWait — but if $ c_a = 0 $ and $ r_b > r_a $, then row $ r_a $ is full, and row $ r_b $ is partial. Then we can select:\n\n- Rectangle 1: rows $ r_a $ to $ r_b - 1 $ (all full rows from $ r_a $ to $ r_b - 1 $) — but if $ r_b = r_a + 1 $, then there are no rows in between, so rectangle 1 is just row $ r_a $, and rectangle 2 is the bottom partial row → 2 selections.\n\nSimilarly, if $ c_b = m - 1 $ and $ c_a > 0 $, then rectangle 1: top partial row, rectangle 2: rows $ r_a + 1 $ to $ r_b $ (which includes full rows and the bottom full row) → 2 selections.\n\nBut if both $ c_a > 0 $ and $ c_b < m - 1 $, and $ r_b > r_a $, then we need 3: top partial, middle full rows (1 rect), bottom partial.\n\nSo the logic is:\n\n```\nif r_a == r_b:\n    return 1\nelif c_a == 0 and c_b == m - 1:\n    return 1\nelif c_a == 0 or c_b == m - 1:\n    return 2\nelse:\n    return 3\n```\n\nBut wait — what if $ r_b = r_a + 1 $, $ c_a = 0 $, $ c_b = m - 1 $? Then it’s covered by the first case: $ c_a = 0 $ and $ c_b = m - 1 $ → return 1, which is correct.\n\nWhat if $ r_b = r_a + 2 $, $ c_a = 0 $, $ c_b = m - 1 $? Then again, entire block is rectangle → 1.\n\nSo the above logic holds.\n\n### Final Answer:\n\n$$\n\\boxed{\n\\begin{cases}\n1 & \\text{if } \\left\\lfloor \\frac{a-1}{m} \\right\\rfloor = \\left\\lfloor \\frac{b-1}{m} \\right\\rfloor \\\\\n1 & \\text{else if } (a-1) \\bmod m = 0 \\text{ and } (b-1) \\bmod m = m - 1 \\\\\n2 & \\text{else if } (a-1) \\bmod m = 0 \\text{ or } (b-1) \\bmod m = m - 1 \\\\\n3 & \\text{otherwise}\n\\end{cases}\n}\n$$\n\nWe can write this more compactly:\n\nLet $ r_a = \\left\\lfloor \\frac{a-1}{m} \\right\\rfloor $, $ r_b = \\left\\lfloor \\frac{b-1}{m} \\right\\rfloor $,  \n$ c_a = (a-1) \\bmod m $, $ c_b = (b-1) \\bmod m $.\n\nThen:\n\n$$\n\\boxed{\n\\begin{cases}\n1 & \\text{if } r_a = r_b \\text{ or } (c_a = 0 \\text{ and } c_b = m - 1) \\\\\n2 & \\text{if } c_a = 0 \\text{ or } c_b = m - 1 \\\\\n3 & \\text{otherwise}\n\\end{cases}\n}\n$$\n\nNote: The second case (2) only applies when the first case (1) does not — so we must ensure ordering.\n\nThus, in code logic:\n\n- if $ r_a == r_b $ → 1\n- else if $ c_a == 0 $ and $ c_b == m-1 $ → 1\n- else if $ c_a == 0 $ or $ c_b == m-1 $ → 2\n- else → 3\n\nBut since the first condition covers single row, and the second condition covers full rectangle spanning multiple rows, the rest are covered.\n\nSo the final answer is:\n\n$$\n\\boxed{\n\\begin{cases}\n1 & \\text{if } \\left\\lfloor \\frac{a-1}{m} \\right\\rfloor = \\left\\lfloor \\frac{b-1}{m} \\right\\rfloor \\text{ or } \\left( (a-1) \\bmod m = 0 \\text{ and } (b-1) \\bmod m = m-1 \\right) \\\\\n2 & \\text{if } (a-1) \\bmod m = 0 \\text{ or } (b-1) \\bmod m = m-1 \\\\\n3 & \\text{otherwise}\n\\end{cases}\n}\n$$","simple_statement":null,"has_page_source":false}