Finding the Replacement Point in the Whisper Game

A group of \(n \times m\) people is divided into \(m\) groups of \(n\) people each. A secret message is split into \(n\) distinct parts and transmitted group by group: from group 1 to group 2, from group 2 to group 3, and so on, until group \(m\). In each transmission, every member in the current group pretends to communicate the message with all \(n\) members in the next group, but only one person in the next group actually receives a message. The arrangement is such that every person in group \(i+1\) receives exactly one message.

When all messages have reached group \(m\), they are read out loud. However, one of the messages has been replaced by a rude word. Originally, the lost (or replaced) message was sent by person \(A\) in group 1, while person \(B\) in group \(m\) read the rude word aloud.

If there had been no replacement, the message from person \(A\) (who is in position \(A\) within group 1) would have been delivered to the person in group \(m\) who occupies the same position. Since people are numbered sequentially, group 1 contains persons \(1\) to \(n\); group 2 contains persons \(n+1\) to \(2n\); and, generally, group \(i\) contains persons \((i-1)n+1\) to \(in\). Thus, the position (or column) of the sender in group 1 is \(c_1 = A\). Similarly, the position of the receiver in group \(m\) is \(c_2 = B - (m-1)n\).

The only way the delivered message could differ from the original is if a replacement occurred during one of the transmissions. In an ideal scenario without replacement the column would remain unchanged; that is, we would have \(c_1=c_2\). However, here \(c_1 \neq c_2\). We define the transmission during which the replacement occurred as the step \(r\) (with \(1\le r\le m-1\)) calculated by

[ r = (c_2 - c_1) \bmod n, ]

with the convention that if \((c_2 - c_1) \bmod n\) equals \(0\) then we set \(r=n\) (although given the problem constraints, \(c_1 \neq c_2\) so \(r\) will be nonzero and, in fact, \(1 \le r \le m-1\)).

Your task is to determine and output the transmission step \(r\) during which the replacement occurred. In other words, the replacement happened during the transmission from group \(r\) to group \(r+1\).

inputFormat

The input consists of a single line containing four integers separated by spaces:

• \(n\): number of people per group,
• \(m\): number of groups,
• \(A\): the number (identifier) of the person in group 1 who originally sent the message,
• \(B\): the number (identifier) of the person in group \(m\) who read out the message.

It is guaranteed that \(1 \le A \le n\) and \( (m-1)n+1 \le B \le mn \), and that the replacement indeed occurred (i.e. \(c_1 \neq c_2\)).

outputFormat

Output a single integer \(r\) which is the transmission step (i.e. the transmission from group \(r\) to group \(r+1\)) during which the replacement occurred.

sample

5 4 2 18

1