Ở thành phố nọ, có một dòng sông đặc biệt. Dòng sông có mô hình như sau:

Con sông chảy theo dạng xoắn, dòng chảy được mô phỏng theo sơ đồ dưới đây:



Lưu ý: Màu mũi tên chỉ có tác dụng giúp bạn đọc dễ phân biệt hướng của dòng chảy chứ không phải hai dòng chảy riêng biệt.

Trên con sông, có nhiều nhà nghỉ nổi được xây dựng. Điều đặc biệt là các nhà nghỉ sẽ có \(a\) phòng đặt theo chiều ngang và \(b\) phòng đặt theo chiều dọc của mỗi vòng. Vị trí các nhà nghỉ được mô phỏng như sau:



Để dễ quản lý, Canuc đặt số thứ tự cho mỗi nhà nghỉ. Canuc sẽ đánh số các phòng ở hàng 1 trước, sau đó là hàng 2, tương tự như vậy đến hàng cuối cùng. Lấy ví dụ như \(n = 4, a = 2, b = 1\). Cách đánh số của các phòng sẽ hoạt động như hình dưới đây:



Sau khi đánh số xong, Canuc liền phát triển dịch vụ ship hàng. Nhờ vào cơ chế đặc biệt của dòng sông, việc ship hàng ở đây vô cùng đơn giản. Chỉ cần thả món đồ cần gửi xuống sông, để trôi, món đồ sẽ tới được phòng cần nhận. Món đồ sẽ trôi xuôi theo chiều dòng nước. Thời gian trôi của món đồ từ một nhà nghỉ đến nhà nghỉ kế tiếp sẽ tốn đúng 1 giây. Hỏi nếu từ nhà số 1, thả trôi theo dòng \(v\) giây, thì món hàng sẽ ở phòng có số thứ tự bao nhiêu?

Input:

Bốn số nguyên dương \(n, a, b, v\)

Output:

Số thứ tự của phòng mà món hàng đang ở sau \(v\) giây.

Ví dụ:

Input:
4 2 1 13

---

Output:
8

---

Giải thích ví dụ

Thả món hàng xuôi theo dòng, nó sẽ lần lượt trôi đến các phòng theo thứ tự sau:
1 -> 2 -> 10 -> 16 -> 17 -> 11 -> 5 -> 6 -> 12 -> 20 -> 21 -> 13 -> 8 -> 7 -> 12 -> 19 -> 18 -> 11 -> 4 -> 3 -> 10 -> 15 -> 14 -> 9 -> 1 -> 2 -> 10 -> 16 -> 17 -> 11 -> 5 -> ...

Vậy, sau 13 giây, món hàng sẽ ở vị trí phòng số 8.

Giới hạn:

• 10% số test \(v \le 10^6\), \(a \le 500\), \(b \le 500\), \(n \le 500\)
  
• 10% số test \(v \le 10^{18}\), \(b = 1\), \(a \le 10^9\), \(n \le 10^9\)
  
• 10% số test \(v \le 10^{18}\), \(a = 1\), \(b \le 10^9\), \(n \le 10^9\)
  
• 10% số test \(v \le 10^{18}\), \(n = 1\), \(a \le 10^9\), \(b \le 10^9\)
  
• 10% số test \(v \le 10^6\), \(10^8 \le a \le 10^9\), \(10^8 \le b \le 10^9\), \(n \le 10^9\)
  
• 50% số test \(v \le 10^{18}\), \(a \le 10^9\), \(b \le 10^9\), \(n \le 10^9\)