n  個(gè)小伙伴（編號(hào)從 0 到 n?1）圍坐一圈玩游戲。按照順時(shí)針方向給 n 個(gè)位置編號(hào)，從 0 到 n?1。最初，第 0 號(hào)小伙伴在第 0 號(hào)位置，第 1 號(hào)小伙伴在第 1 號(hào)位置，……，依此類推。

游戲規(guī)則如下：每一輪第 0 號(hào)位置上的小伙伴順時(shí)針走到第 m 號(hào)位置，第 1 號(hào)位置小伙伴走到第 m+1 號(hào)位置，……，依此類推，第 n?m 號(hào)位置上的小伙伴走到第 0 號(hào)位置，第 n?m+1 號(hào)位置上的小伙伴走到第 1 號(hào)位置，……，第 n?1 號(hào)位置上的小伙伴順時(shí)針走到第 m?1 號(hào)位置。

現(xiàn)在，一共進(jìn)行了 10^k 輪，請(qǐng)問 x 號(hào)小伙伴最后走到了第幾號(hào)位置。

輸入共 1 行，包含 4 個(gè)整數(shù) n、m、k、x，每兩個(gè)整數(shù)之間用一個(gè)空格隔開。

輸出共 1 行，包含 1 個(gè)整數(shù)，表示 10^k 輪后 x 號(hào)小伙伴所在的位置編號(hào)。

數(shù)據(jù)范圍與提示：

對(duì)于 30% 的數(shù)據(jù)，0<k<7；

對(duì)于 80% 的數(shù)據(jù)，0<k<10⁷ ；

對(duì)于 100% 的數(shù)據(jù)，1<n<10⁶，0<m<n，1≤x≤n，0<k<10⁹。

信息學(xué)一本通 數(shù)學(xué)