Trong tiết học môn toán về chủ đề tìm ước chung lớn nhất và bội chung nhỏ nhất của hai số nguyên dương \(A\) và \(B\), Bình dễ dàng tìm được \(UCLN(A,B)\) là \(m\) ,\(BCNN(A,B)=n\). Hôm nay, cô giáo đưa ra bài toán sau:
"Cho trước hai số nguyên \(m\) và \(n\), nếu tìm được một hoặc nhiều cặp số \((A,B)\) thỏa mãn \(UCLN(A,B)\) là \(m\) ,\(BCNN(A,B)=n\) thì đưa ra giá trị nhỏ nhất của tổng \(A+B\), ngược lại thì đưa ra \(-1\)."
Bình đang loay hoay tìm cách giải, hãy giúp Bình giải bài toán trên.

Yêu cầu:

• Tìm giá trị nhỏ nhất của tổng \(A+B\), nếu không tìm được cặp số \((A,B)\) nào thì đưa ra \(-1\).

INPUT:

• Hai số nguyên dương \(m\) và \(n\) cách nhau bởi dấu cách.

OUTPUT:

• Kết quả tìm được.

Constraints:

• \(1 \le m,n \le 10^{12}\).

Example:

2 10

12

2 20

14

3 5

-1

Cho số tự nhiên \(A\) và biểu thức sau:

Yêu cầu: Hãy sử dụng phép tính \(+, -, \times\) điền vào \(?\) để được \(B\) lớn nhất.

Input

• Nhập vào một số tự nhiên \(A\) \((0 \leq A \leq 100)\).

Output

• Ghi ra số \(B\) lớn nhất tìm được.

Example

5

25

1

2

Ông Từ đang ôn bài tập về dãy số, hôm nay ông có \(1\) dãy số \(a\) gồm \(n\) phần tử, đối với ông \(1\) dãy con liên tiếp của \(a\) được xem là dãy đẹp nếu số lượng phần tử của dãy con đó không bé hơn giá trị bé nhất trong dãy con và không lớn hơn giá trị lớn nhất trong dãy con.
Hay nói cách khác, đoạn con từ \(i\) đến \(j\) được xem là đẹp nếu \(Min(a_i, a_{i + 1},...a_j) \le j - i + 1 \le Max(a_i, a_{i + 1},...a_j)\). Ông Từ muốn tính số cách chia dãy thành các đoạn đẹp sao cho mỗi phần tử phải thuộc duy nhất \(1\) đoạn đẹp. Vì số cách có thể rất lớn nên bạn hãy in số cách dưới dạng modulo cho \(10^9 + 7\) giúp ông nhé.

Input

• Dòng đầu tiên ghi số \(n\) \((1 \le n \le 10^5)\);
• Dòng tiếp theo gồm \(n\) số mô tả mảng \(a\) \((1 \le a_i \le n)\).

Output

• Gồm \(1\) số nguyên là kết quả bài toán.

7
1 6 2 3 4 3 4

6

Peter có \(1\) bộ bài gồm \(n\) lá, với các lá được đánh số từ \(1\) đến \(n\), lá thứ \(i\) có mặt trên là giá trị \(a_i\) và mặt dưới là giá trị \(b_i\). Bạn hãy giúp Peter lật hoặc úp các lá bài sao cho số lượng giá trị khác nhau hiện lên ở trên là nhiều nhất có thể biết rằng bạn có thể lật hoặc úp vô số lần.

Input

• Dòng đầu tiên ghi số \(n\) \((1 \le n \le 10^5)\);
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(2\) số \(a_i\) và \(b_i\) \((1 \le a_i, b_i \le n)\)

Output

• Gồm \(1\) số nguyên dương là kết quả bài toán.

Example

4
1 2
1 3
4 2
2 3

4