Cho bốn số nguyên dương ~a, b, c, d~, mỗi số có giá trị không vượt quá ~10^5~.

Yêu cầu: Tìm hai số nguyên ~x, y~ để phân số ~x \over y~ tối giản và bằng hiệu của hai phân số ~\frac{a}{b} - \frac{c}{d}~, trong đó ~y > 0~.

Dữ liệu: Vào từ tệp văn bản CAU1.INP:

• Dòng đầu chứa hai số ~a, b~;
• Dòng thứ hai chứa hai số ~c, d~.

Kết quả: Ghi ra tệp văn bản CAU1.OUT

Hai số ~x~ và ~y~ trên cùng một dòng, cách nhau một dấu cách.

Ví dụ:

Input

1 6
5 12

Output

-1 4

Cho một mảng ~a~ gồm có ~n~ phần tử.

Ta quy ước việc ghép ba số bất kì là việc viết các số liên tiếp nhau theo thứ tự bất kì.

Ví dụ: Với ba số ~123~, ~45~, ~678~, ta có thể ghép ba số này thành các số:

• ~12345678~
• ~12367845~
• ~45123678~
• ~45678123~
• ~67812345~
• ~67845123~

Chọn ba số bất kì từ mảng ~a~. Hỏi giá trị lớn nhất ta có thể nhận được từ việc ghép số ba số đó là bao nhiêu?

Input

Dòng đầu tiên gồm số nguyên dương ~n~ - số lượng phần tử của mảng ~a~ (~3 \le n \le 2*10^5~).

Dòng tiếp theo chứa ~n~ số nguyên dương - các phần tử của mảng ~a~ (~a_i \le 10^9~, ~i = 1...n~)

Output

In ra một số duy nhất là đáp án bài toán.

Sample Input 1

5
6 1 8 10 9

Sample Output 1

9810

Giải thích: Ta chọn ba số ~9~, ~8~, ~10~ và sau đó ghép thành số ~9810~. Đây là số lớn nhất ta có thể ghép được.

Cho dãy số ~a~ nguyên không âm gồm ~n~ phần tử ~a_1~, ~a_2~, ~a_3~,~...~,~a_n~ và số nguyên dương ~k \le n~.

Hãy tìm cách chia dãy số thành ~k~ đoạn con liên tiếp sao cho chênh lệch giữa đoạn có tổng các phẩn tử lớn nhất và đoạn có tổng các phần tử nhỏ nhất là bé nhất.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ (~k \le n \le 250~, ~k \le 50~).

Dòng tiếp theo chứa các phần tử của dãy ~a~ (~0 \le a_i < 10^6~, ~i=1,2,..n~).

Output

In ra một số duy nhất là đáp án bài toán.

Sample Input 1

6 3
7 4 6 1 2 10

Sample Output 1

2

Giải thích: Ta chia thành ba đoạn như sau: ~[7,4]~, ~[6,1,2]~, ~[10]~.

Các đoạn lần lượt có tổng là ~11~, ~9~, ~10~. Vậy độ chênh lệch của cách chia này là ~2~.

Có thể chứng minh rằng không tồn tại cách chia nào khác có độ chênh lệch nhỏ hơn ~2~, do đó, chênh lệch nhỏ nhất có thể là ~2~.