Ở quán ăn sáng nọ có ~𝑛~ khách quen. Mỗi vị khách cứ sau một số ~𝑦~ ngày nhất định sẽ đến quán ăn đó để ăn sáng. Biết rằng xuất phát điểm ban đầu tất cả các vị khách quen sẽ đến ăn sáng vào ngày đầu tiên. Bạn hãy giúp chủ quán tính xem sau bao nhiêu ngày thì tất cả các vị khách quen của quán mới lại cùng đến ăn sáng cùng ngày và khi đó mỗi vị khách đã đến quán ăn bao nhiều lần.

Dữ liệu vào:

• Dòng đầu chứa số nguyên n (~2 ≤ 𝑛 < 100~)
• Dòng thứ hai chứa n số nguyên ~𝑦~. (~1 ≤ 𝑦 < 100~)

Dữ liệu ra:

• Dòng đâu tiên ghi ra số ngày mà tất cả các vị khách cùng đến quán ăn.
• Dòng thứ hai chứa n số là số lần một vị khách đã đến quán ăn cho tới lúc tất cả cùng đến.

Ví dụ

Input

3
2 3 4

Output

12
6 4 3

Hai bạn An và Bách cùng học một trường nhưng ở 2 lớp khác nhau. An cứ a ngày lại trực nhật một lần; Bách cứ b ngày lại trực nhật một lần. Lần đầu cả hai người cùng trực nhật vào cùng một ngày. Hỏi sau ít nhất bao nhiêu ngày thì hai bạn lại cùng trực nhật cùng ngày? Lúc đó mỗi bạn đã trực nhật được bao nhiêu lần?

Dữ liệu vào:

• 2 số nguyên a,b.(~1 \le a,b \le 200000~)

Dữ liệu ra:

• In ra theo ví dụ sau

Ví dụ:

Input

10
12

Output

60
An: 6
Bach: 5

Mặt phẳng trong hệ tọa độ Đề Các được chia thành 4 phần (xem hình vẽ).

Cho hoành độ ~𝑥_𝑎~ và tung độ ~𝑦_𝑎~ của điểm ~𝐴~.

Yêu cầu: Hãy cho biết điểm ~𝐴~ thuộc phần nào?

Dữ liệu vào:

• Hai số thực ~𝑥_𝑎,𝑦_𝑎~

Giới hạn:

• ~0<|𝑥_𝑎|,|𝑦_𝑎|≤10^9~

Kết quả:

• Ghi một số là kết quả của bài toán.

Ví dụ:

Input

2.35 -4.6

Output

4

Vừa gà vừa chó

Bó lại cho tròn

Tổng n con

Và k chân chẵn

Yêu cầu: Tính số gà, số chó biết n, k là 2 số nguyên dương cho trước.

Input:

• Nhập vào 2 số nguyên dương n, k.

Output:

• Ghi 2 số nguyên x,y tương ứng là số gà số chó tìm được. Nếu không tìm được x,y thỏa mãn thì ghi -1.

Example:

Input:

36 100

Output:

22 14

Constraints:

~0 < n < k < 2*10^9~

28techland là vùng đất mà cư dân cực kì thích uống bia, vì thế để tăng số lượng bia bán ra các cửa hàng bia ở đây đưa ra khuyến mại như sau : Cứ 3 vỏ chai bia sẽ được đổi một chai bia mới. Biết rằng ở 28techland, mỗi chai bia có giá 28 xu, nhiệm vụ của bạn là xác định với N xu cho trước, bạn có thể mua được tối đa bao nhiêu chai bia tính cả việc đổi thưởng bằng vỏ chai?

Gợi ý : Bước 1 : Tính số lượng chai bia mua bằng tiền (n / 28). Sau đó làm 1 vòng lặp while với điều kiện lặp là số lượng vỏ chai mình có >= 3, bên trong vòng lặp thì tính số lượng chia bia đổi được và cập nhật vỏ chai.

Input Format

Dòng duy nhất chứa N là số đồng xu ban đầu

Constraints

1<=N<=10^6

Output Format

In ra số lượng chai bia tối đa có thể mua

Sample Input 0

138

Sample Output 0

5

Giải thích sample00

138 xu có thể mua được 4 chai bia, 4 vỏ chai của chai bia này sẽ đổi thêm được 1 chai bia nữa. Kết quả tổng số chai bia có thể mua là 5.

Công ty XD chuyên sản suất gạch xây tường, khi các viên gạch ra lò chờ xuất bán, các viên gạch được sắp thành hình tháp. Có ~N~ hàng gạch, hàng trên cùng có ~A~ viên gạch. Biết hàng dưới nhiều hơn hàng kề trên ~B~ viên. Hỏi để xếp được ~N~ hàng gạch đó người ta đã dùng bao nhiêu viên gạch?

Dữ liệu:

• Một dòng chứa 3 số nguyên ~N~, ~A~, ~B~.

Kết quả:

• Số nguyên duy nhất – số lượng viên gạch đã dùng.

Ví dụ

Input

5 1 1

Output

15

Giới hạn:

• ~N ≤ 2.10^{12} ; A ≤ 20; B ≤ 20~.

Cho dãy số nguyên gồm các số từ ~1 -> n~ . Tìm cách chèn ~(n-1)~ dấu ~'+'~ hoặc ~'–'~ vào giữa các số sao cho khi tính biểu thức đó cho kết quả là ~S~.

Yêu cầu: chèn ít dấu trừ nhất có thể

Input :

• Cho ~n~ và ~S~ (~1 ≤ n ≤ 500, |S| ≤ 125250~)

Output :

• Nếu có xuất ra biểu thức, không thì xuất 'Impossible'

Ví dụ:

Input:

9 5

Output:

1+2-3+4+5+6+7-8-9

Input:

5 6

Output:

Impossible

Ước số chung của dãy số nguyên dương là các số nguyên dương mà tất cả các số trong dãy đều chia hết cho nó. Hôm nay, Tuấn đang học về ước số chung và Tuấn được thầy giáo cho bài toán: Có một dãy số ~A~ gồm ~N~ số nguyên dương, hãy tìm ước số chung nhỏ nhất khác 1. Nói cách khác, Tuấn cần tìm số D nhỏ nhất, sao cho ~D >1~ và các số trong dãy số ~A~ đều chia hết cho số ~D~ này.

Yêu cầu: Cho một số ~A~ gồm ~N~ số nguyên dương, hãy giúp Tuấn đưa ra số là Ước số chung nhỏ nhất khác 1.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N≤10^5~)
• Dòng tiếp theo gồm ~N~ số nguyên dương ~A_i~​ là các phần tử của dãy ~A~ (~A_i≤10^6~).

Output

• Một số nguyên dương ước chung nhỏ nhất của dãy số. Nếu không tồn tại số nào, in ra -1.

Scoring

• Subtask 1 (60% số điểm): N≤10^3, ~A_i≤10^5~.

• Subtask 2 (40% số điểm): Không có ràng buộc gì thêm

Example

Test 1

Input

3
1 2 3

Output

-1

Test 2

Input

3
2 4 6

Output

2