Cho \(N\) số tự nhiên từ \(1\) đến \(N\) được đặt lần lượt trên một vòng tròn (số thứ \(N\) kề với số \(1\)).
Người ta thực hiện xóa lần lượt các số khỏi vòng tròn theo quy tắc:

• Bắt đầu từ số \(X\), xóa số đó khỏi vòng tròn
• Mỗi lượt tiếp theo, đếm \(K\) bước theo chiều kim đồng hồ (bỏ qua số đã xóa), xóa số thứ \(K\)
• Lặp lại cho đến khi vòng tròn rỗng

Giả sử với \(N=5\), bắt đầu xóa ở vị trí \(X=2\), chu kì \(K=3\) thì các bước xóa lần lượt như sau:

Yêu cầu

Tìm vị trí lượt xóa (thứ mấy) của số \(M\) trong quá trình mô phỏng xóa trên vòng tròn.

Input

• Dòng 1: Số nguyên \(N\) là số lượng số ban đầu trên vòng tròn (\(1 \leq N \leq 10^5\))
• Dòng 2: Số nguyên \(X\) là vị trí bắt đầu (\(1 \leq X \leq N\))
• Dòng 3: Số nguyên \(K\) là bước đếm (\(1 \leq K \leq N\))
• Dòng 4: Số nguyên \(M\) là số cần theo dõi (\(1 \leq M \leq N\))

Output

• Một dòng duy nhất ghi số thứ tự lượt xóa của số M
• Nếu \(M\) không bị xóa thì in ra 0

Example

4
2
2
3

3

6
3
4
4

6

Scoring

• Subtask \(1\) (\(30\) điểm): \(N, K \leq 100\)
• Subtask \(2\) (\(30\) điểm): \(N, K \leq 10\,000\)
• Subtask \(3\) (\(40\) điểm): \(N, K \leq 100\,000\)