Finding the Optimal Stable Card Location

The Great Cardoni, a master prestidigitator, has long used a card trick with 21 cards arranged into a 3‐column grid. In his trick the spectator secretly chooses a card (by number) from a deck laid out row–by–row, and then repeatedly indicates the column containing the chosen card. After each indication the magician collects the cards by columns, but with one twist: the column that contains the secret card is always picked up in a prescribed position (traditionally, the second pile). After a few iterations the originally selected card moves into a fixed, or stable position — in the classic case, the center card of the grid.

Now Cardoni wishes to generalize the trick. Given an arrangement of R rows and C columns it is possible, by suitably choosing the order in which the magician picks up the columns (with the constraint that when a spectator indicates a column, that column is picked up in a predetermined position), to force every card (regardless of its starting location) to converge to the same stable location. Moreover, Cardoni wants this unique stable location to be as close as possible to the center of the grid.

The procedure is as follows. By an appropriate strategy the magician forces that, whenever the spectator indicates a column, exactly t columns (each having R cards) are collected before the indicated column. (Note that t may depend on the chosen strategy and can be any integer between 0 and C−1.) Then, if a card originally in row r of the indicated column is in that column when it is picked up, its new position in the deck is given by

$$p' = t\,R + r,$$

and when the deck is redealt row–by–row into an R×C grid its new location becomes

$$\text{row} = \left\lceil \frac{tR+r}{C} \right\rceil, \quad \text{column} = \left(((tR+r)-1)\bmod C\right)+1. $$

Call the function

$$f_t(r) = \left\lceil \frac{tR+r}{C} \right\rceil. $$

By iterating this process (that is, replacing r by f_t(r) repeatedly) the location of the chosen card will eventually converge to a stable row r* (with corresponding column given by $$ c^* = \Bigl(((tR+r^*)-1)\bmod C\Bigr)+1). $$

A strategy (i.e. a choice of t together with appropriate instructions on how to pick up the remaining columns) is valid if the iterative process has a unique attractor (r*, c*) that is reached regardless of the initial row value. Cardoni wishes to choose, among all valid strategies (t values such that the iteration converges to the same fixed point regardless of starting row), the one for which the resulting stable location is as close as possible to the center of the R×C grid. (The center is defined to be at \(\left(\frac{R+1}{2}, \frac{C+1}{2}\right)\).)

Your task is to help Cardoni. Given R and C as input, consider all integers t with \(0 \le t \le C-1\). For each t let the fixed point be determined by iterating $$ r \leftarrow f_t(r)=\left\lceil \frac{tR+r}{C} \right\rceil $$ starting from r=1 and from r=R until convergence. If both starting values lead to the same fixed point r*, define the resulting stable grid location to be $$ (r^*, c^*) \quad \text{with} \quad c^*=\Bigl(((tR+r^*)-1)\bmod C\Bigr)+1. $$ Among all t for which the stable location is unique, choose the one whose stable location \((r^*, c^*)\) minimizes the Euclidean distance to the grid’s center \(\left(\frac{R+1}{2}, \frac{C+1}{2}\right)\). If there is a tie, choose the one with the smaller row number. If no valid t exists, output "0 0".

Input Format: Two integers R and C representing the number of rows and columns.

Output Format: Two integers indicating the row and column of the stable location.

inputFormat

The input consists of a single line containing two space‐separated positive integers R and C (with R being the number of rows and C the number of columns).

outputFormat

Output two integers separated by a space – the row and column index (1–indexed) of the unique stable location achieved by the optimal strategy. If no valid strategy exists, output "0 0".

sample

7 3

4 2