Người dân ven sông Tô Lịch xếp ~n + 1~ hòn đá trên một đường thẳng vuông góc với hai bờ để làm lối đi qua sông. Các hòn đá được đánh số từ ~0~ đến ~n~ theo thứ tự; hòn đá ~0~ sát một bờ, hòn đá ~n~ sát bờ bên kia.

Họ chọn một số nguyên dương ~M~ và quy định khoảng cách giữa hai hòn đá liên tiếp như sau: với mỗi ~i~ thỏa ~0 \le i < n~, khoảng cách từ hòn đá ~i~ đến hòn đá ~i + 1~ là ~d_i = 1 + (i^2 \bmod M)~ (trong đó ~\bmod~ là phép lấy phần dư).

Ví dụ với ~n = 5~ và ~M = 7~ (sách ghi nhầm ~M = 2~ nhưng các phép tính đều dùng modulo 7):

• ~d_0 = 1 + (0^2 \bmod 7) = 1~
• ~d_1 = 1 + (1^2 \bmod 7) = 2~
• ~d_2 = 1 + (2^2 \bmod 7) = 5~
• ~d_3 = 1 + (3^2 \bmod 7) = 3~
• ~d_4 = 1 + (4^2 \bmod 7) = 3~

Mọi người muốn qua sông trong không quá ~j~ bước nhảy. Mỗi bước nhảy xuất phát từ một hòn đá và đáp xuống một hòn đá khác; bước đầu tiên bắt đầu ở hòn đá ~0~ và bước cuối cùng kết thúc ở hòn đá ~n~. Hãy tìm tầm nhảy nhỏ nhất, tức số ~L~ nhỏ nhất sao cho có thể đi từ hòn đá ~0~ tới hòn đá ~n~ bằng không quá ~j~ bước nhảy, mỗi bước có độ dài (khoảng cách) không quá ~L~.

Dữ liệu

• Một dòng duy nhất gồm ba số nguyên dương ~n, M, j~ (~1 \le j \le n \le 10^6~, ~1 \le M \le 10^9 + 7~).

Kết quả

• In ra một số nguyên dương duy nhất là tầm nhảy nhỏ nhất để qua sông với không quá ~j~ bước nhảy.

Ví dụ

Ví dụ 1

RIVER.INP

10 1 1

RIVER.OUT

10

Ví dụ 2

RIVER.INP

10 1 10

RIVER.OUT

1

Ví dụ 3

RIVER.INP

10 22071997 10

RIVER.OUT

82

Giới hạn

• Subtask 1 (20% số điểm): ~j = M = 1~.
• Subtask 2 (20% số điểm): ~j = n~.
• Subtask 3 (60% số điểm): không có ràng buộc gì thêm.