Bài tập

Cho ba số nguyên dương $ a, b, m $ \(( 1 \leq a < b \leq 10^4, 1 < m \leq 10^9 )\).

Yêu cầu: Tìm số dư của phép chia tích các số trong đoạn \([a..b]\) cho $ m $.

Input

File MOD.INP chứa ba số $ a, b, m $ cách nhau dấu cách.

Output

File MOD.OUT chứa kết quả phép chia.

Example

1 5 10

0

Bạn cần mua chính xác \(N\) lít xăng. Một trạm xăng cung cấp hai lựa chọn mua:

• Mua \(1\) lít xăng với giá \(a\) đồng.
• Mua \(2\) lít xăng với giá \(b\) đồng.

Mục tiêu của bạn là tìm ra cách mua xăng với chi phí thấp nhất.

Với ba số nguyên dương \(N\), \(a\), và \(b\) cho trước, hãy tính chi phí tối thiểu để mua đúng \(N\) lít xăng.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn (stdin) theo định dạng sau:

• Dòng đầu tiên chứa một số nguyên dương \(N\) (\(1 \le N \le 10^9\)), là lượng xăng bạn cần mua.
• Dòng thứ hai chứa hai số nguyên dương \(a\) và \(b\) (\(1 \le a, b \le 10^9\)), là giá của \(1\) lít và \(2\) lít xăng tương ứng.

Output

In ra một số nguyên duy nhất là chi phí tối thiểu để mua chính xác \(N\) lít xăng.

Example

5
1 1

3

7
1 7

7

Máy tính dùng dãy bít hay còn gọi là dãy nhị phân chỉ bao gồm hai kí hiệu \(0\) và \(1\) để biểu diễn các số trong tính toán. Em hãy viết chương trình giúp máy tính chuyển một số nguyên dương \(N\) (hệ thập phân) sang dãy nhị phân (hệ nhị phân) với \(1 \leq N \leq 10^9\).

Input

Dữ liệu vào: Từ tệp văn bản nhiphan.inp chứa duy nhất số nguyên dương N.

Output

Dữ liệu ra: Ghi ra tệp văn bản nhiphan.out chứa dãy nhị phân.

Example

12

1100

Scoring

• \(75\%\) số test tương ứng \(75\%\) số điểm với \(1 \leq N \leq 10^6\)
• \(25\%\) số test tương ứng \(25\%\) số điểm với với \(10^6 \leq N \leq 10^9\)

Viết chương trình nhập từ bàn phím một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\). Hãy tìm và in ra giá trị lớn nhất trong mảng.

Input

• Dòng đầu tiên là số nguyên dương \(n\) - độ dài của dãy \(a\). \((1 \leq n \leq 100)\).
• Dòng thứ hai là \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) - mỗi số cách nhau một dấu cách \((|a_i| \leq 100)\).

Output

Một dòng duy nhất chứa giá trị lớn nhất của mảng.

Example

5
3 2 1 5 2

5