Description

伟大的魔术师 Cardoni 拥有一副编号为 1 到 21 的牌，他用这副牌进行一个魔术表演。观众秘密选择一个 1 到 21 之间的数字，然后 Cardoni 将 21 张牌面朝上按顺序从 1 到 21 逐行发到一个 3 列的网格中。观众随后指出三列中的哪一列包含所选的牌，此时魔术师按列收起牌，第二个收起观众指定的列（收集其他两列的顺序不重要）。牌是面朝上收集的，从每列的顶部牌开始，每张后续的牌立即放在前一张牌的下面。然后从面朝上的牌堆顶部开始逐行重新发牌到一个 3 列的网格中。这个过程重复两次；每次观众指定的列都是魔术师第二个收起的列。经过三次这样的迭代后，Cardoni 宣布：“我已经洞察了你的心灵；你的牌就在这个展示的中心。”这是真的——所选的牌位于数组的“中心”（第 4 行，第 2 列）。而且，对于任何进一步的列指示和重新发牌过程，所选的牌将始终保持在这个稳定的位置。这个过程总是有效的，无论选择的数字是多少，只要包含秘密数字的列是第二个被收起和重新发牌的列。Cardoni 希望扩展他的魔术，使用不同数量的牌、行和列，并尝试在观众指示列后以不同的顺序收起列。然而，这不是一个简单的问题。例如，当使用 24 张牌在 8 行 3 列中，并且始终将指示的列作为第二个重新发牌的列时，数字 5 最终会在稳定位置第 4 行第 3 列，而数字 20 最终会在稳定位置第 5 行第 1 列。此外，这两个位置都不是第 4 行或第 5 行第 2 列的两个“中心”位置之一。此外，Cardoni 不确定在选定的牌到达稳定位置之前需要多少次“指示列和重新发牌”过程的迭代。给定卡牌的行数和列数，帮助 Cardoni 设置他的魔术，使得有一个唯一的稳定位置尽可能靠近中心。

Input Format

输入由一行包含两个整数 $r$ 和 $c$（$2 \le r, c \le 10^6$）组成，表示魔术中使用的行数和列数。牌从 1 到 $r \cdot c$ 编号，最初按行按升序发牌。

Output Format

输出一行包含四个整数 $p$、$i$、$j$ 和 $s$，其中：

• 观众指示的列应作为第 $p$ 列收起，
• 使用这个 $p$ 值会导致所有牌最终到达第 $i$ 行第 $j$ 列的稳定位置，
• $s$ 是任何牌到达稳定位置所需的最大迭代次数。

$p$ 的值应选择使得稳定位置 $(i, j)$ 尽可能接近网格中的一个、两个或四个中心位置，其中位置 $(i, j)$ 和 $(i', j')$ 之间的距离为 $|i-i'| + |j-j'|$。如果多个 $p$ 值导致相同的最小距离，则选择最小的 $p$。

7 3

2 4 2 3

8 3

1 1 1 3

Hint

题面翻译由 ChatGPT-4o 提供。