题目背景

ICPC2020 WF A

题目描述

The Great Cardoni, Master Prestidigitator, has a deck of 21 numbered cards which he uses in a trick as follows:

A spectator secretly selects a number between $1$ and $21$, inclusive, after which Cardoni deals the $21$ cards, face-up, row by row in order from $1$ to $21$, into a $3$-column grid. The spectator then indicates which of the three columns contains the selected card, at which point the magician picks up the cards by columns, picking up the specified column second (the order of collecting the other two columns is unimportant). Cards are collected face up, beginning with the top card in each column and placing each succeeding card immediately beneath the previously collected card. The cards are then redealt by rows into a $3$-column grid, starting from the top of the face-up deck. The process is repeated two more times; each time, the column indicated by the spectator is the second column picked up by the magician. After three such iterations, Cardoni announces, "I have penetrated to the heart of your mind; your card lies at the heart of this display." And it's true---the selected card is located at the "heart" of the array (row four, column two). Moreover, the selected card will always remain in this stable location for any further iterations of the column indication and card redealing process.

The process always works, no matter the number selected, provided that the column containing the secret number is the second column to be picked up and redealt.

Cardoni would like to expand his trick to use different numbers of cards, rows, and columns, and to experiment with different orderings of picking up the columns after the spectator indicates a column. However, it is not a trivial problem. For instance, when using $24$ cards in $8$ rows and $3$ columns, and always picking up the indicated column as the second one to redeal, the number $5$ eventually ends up in stable location row $4$, column $3$, while the number $20$ ends up in stable location row $5$, column $1$. Also, neither location is one of the two "heart" positions in column $2$ of rows $4$ or $5$. Moreover, Cardoni is uncertain of how many iterations of the "indicate column and redeal" process are needed before a selected card reaches a stable location.

Given the number of rows and columns of cards, help Cardoni set up his trick in such a way that there is a unique stable location that is as close to the center as possible.

输入格式

The input consists of a single line with two integers $r$ and $c$ ($2 \le r, c \le 10^6$), the number of rows and columns used in the trick. The cards are numbered from $1$ to $r \cdot c$ and are initially dealt row by row in increasing order.

输出格式

Output a line containing four integers $p$, $i$, $j$, and $s$, where:

• the column indicated by the spectator should be picked up as the $p^{\text{th}}$ column,
• using this value of $p$ causes all cards to eventually end up in the stable location at row $i$ column $j$, and
• $s$ is the maximum number of iterations required for any card to reach the stable location.

The value of $p$ should be chosen so that the stable location $(i, j)$ is as close as possible to any of the one, two or four central positions in the grid, where the distance between locations $(i, j)$ and $(i', j')$ is $|i-i'| + |j-j'|$. If more than one value of $p$ results in the same minimum distance, choose the smallest such $p$.

题目大意

观众秘密地选择一个介于1和21之间（包括1和21）的数字，然后卡多尼将这21张牌面朝上，按1到21的顺序逐行放入一个3列的网格中。然后观众指出三列中的哪一列包含所选的牌，此时魔术师逐列拾取牌，然后拾取指定的列（收集其他两列的顺序不重要）。卡片收集时面朝上，从每列中最上面的卡片开始，然后将随后的每张卡片放在之前收集的卡片的正下方。然后，从正面朝上的卡片组顶部开始，将卡片按行重新排列到3列的网格中。该过程再重复两次；每一次，观众指示的柱是魔术师拾取的第二个柱。在三次这样的反复之后，卡多尼宣布：“我已经深入到了你的内心；你的牌位于这张展示的核心。”这是真的——所选的卡位于数组的“中心”（第四行，第二列）。此外，所选卡将始终保持在该稳定位置，以便进一步迭代列指示和卡重新调整过程。

只要包含机密号的列是要拾取和重新替换的第二列，则无论选择的数字是多少，该过程始终有效。

卡多尼想扩展他的技巧，使用不同数量的卡片、行和列，并在观众指示一列后，尝试不同的顺序拾取列。然而，这不是一个微不足道的问题。例如，当在8行3列中使用24张卡，并始终将指示列作为第二个重新指定的列时，数字5最终会在稳定位置第4行第3列结束，而数字20最终在稳定位置第5行第1列结束。此外，两个位置都不是第4行或第5行第2列中的两个“心脏”位置之一。此外，Cardoni不确定在选定的卡到达稳定位置之前，需要多少次“指示列和重新指定”过程的迭代。

考虑到卡片的行数和列数，帮助卡多尼设置他的技巧，使其有一个独特的稳定位置，尽可能靠近中心。

数据范围

$2 \le r, c \le 10^6$（r行c列）

7 3

2 4 2 3

8 3

1 1 1 3