Nhân dịp xuân về, đội văn nghệ của nhà văn hóa thiếu nhi được cử đi biểu diễn giao lưu ở các phường trong thành phố. Đội văn nghệ có ~n~ bạn học sinh nam và ~m~ bạn học sinh nữ được chia thành các tổ, mỗi tổ sẽ đi phục vụ văn nghệ cho người dân ở các phường khác nhau. Biết rằng: số lượng học sinh nam và số lượng học sinh nữ phải được chia đều giữa các tổ và sau khi chia tổ, mỗi học sinh đều thuộc một tổ.

Yêu cầu: Em hãy cho biết đội văn nghệ có thể chia nhiều nhất bao nhiêu tổ? Mỗi tổ có bao nhiêu nam và bao nhiêu nữ.

Dữ liệu vào:

Được cho bởi tệp VANNGHE.INP:

• Gồm một dòng duy nhất chứa 2 số nguyên ~n~, ~m~ giữa 2 số cách nhau một dấu cách (~1 ≤ n, m ≤ 10^{12}~)

Dữ liệu ra:

Được cho bởi tệp VANNGHE.OUT:

• Dòng 1. Ghi một số nguyên là số lượng tổ tối đa có thể chia được.
• Dòng 2. Ghi hai số a, b tương ứng là số học sinh nam và số học sinh nữ của mỗi tổ, giữa 2 số cách nhau một dấu cách.

Ví dụ:

Input

48 72

Output

24
2 3

Số trong xâu được hiểu là tập hợp các ký tự số đứng liền nhau: Ví dụ: ~S='nb234nm76nm8'~ có 3 số xuất hiện trong xâu ~S~ là: 234, 76,8. Cho xâu ký tự ~S~ được đọc ra từ tệp .

Yêu cầu: Tìm số chính phương lớn nhất không xuất hiện trong xâu, biết rằng các số xuất hiện trong xâu có không quá 9 chữ số và số chính phương lớn nhất tìm được phải nhỏ hơn hoặc bằng số lớn nhất trong xâu.

Input:

• Nhập vào một xâu ký tự ~S~.

Output:

• In ra số chính phương lớn nhất không xuất hiện trong xâu s theo yêu cầu trên.

Example:

Input:

nb2nm76nm8j3733

Output:

3721

Constraints:

~0 < length(S) \le 10^6~

Hôm qua Bờm mới học về số tự kỷ (số tự kỷ là một số tự nhiên có tổng các ước thực sự nhỏ hơn nó). Ví dụ: ~N=8~ là một số tự kỷ vì N có tổng các ước thực sự: 1 + 2 + 4 = 7 < 8. Sau khi làm xong bài đếm số lượng các số tự kỷ trong đoạn từ a đến b (~a ≤ b~), Bờm nghĩ ra bài toán như sau: Với một số nguyên dương ~k~ biết trước, khi độ dài d (~1 ≤ d ≤ b - a + 1~) nhỏ nhất là bao nhiêu để với mọi đoạn con độ dài d của đoạn [~a, b~] đều có ít nhất ~k~ số tự kỷ. (Một đoạn con độ dài ~d~ của đoạn [~a~, ~b~] bắt đầu từ ~c~ (~a ≤ c ≤ b - d + 1~) gồm các số ~x, x + 1, ..., x + d - 1~).

Yêu cầu: Hãy giúp Bờm tìm giá trị của ~d~.

Dữ liệu vào: Đọc từ tệp văn bản DOANSTK.INP gồm một dòng duy nhất ghi ba số a, b, k cách nhau một dấu cách (~1 ≤ a ≤ b~, ~1 ≤ k ≤ 10^6~).

Kết quả: Ghi ra tệp văn bản DOANSTK.OUT một số duy nhất d, nếu không có d ghi -1.

Ví dụ:

Input1:

2 4 3

Output1:

3

Input2:

2 7 3

Output2:

4

Một nhà máy sản xuất gồm có hai phân xưởng: phân xưởng nhận và phân xưởng vẽ. Ban đầu tất cả các sản phẩm được hình thành từ phân xưởng nhận, sau đó được chuyển sang phân xưởng vẽ để hoàn tất sản phẩm trước khi nung. Do hai phân xưởng này ở các vị trí khác nhau nên trong một ngày tất cả các công đoạn sản xuất chỉ được vận chuyển một lần duy nhất từ phân xưởng nhận sang phân xưởng vẽ bằng một ô tô chuyên dụng. May mắn là thời gian vận chuyển xem như bằng 0. Sau khi hoàn thành xong, toàn bộ sản phẩm sẽ ngay lập tức đem đi nung.

Phân xưởng nhận có ~N~ thợ thủ công, thợ thứ ~i~ hoàn thành một sản phẩm mất ~a_i~ đơn vị thời gian. Phân xưởng vẽ có ~M~ thợ thủ công, thợ thứ ~j~ hoàn thành một sản phẩm mất ~b_j~ đơn vị thời gian. Ngày làm việc kéo dài ~T~ đơn vị thời gian. Khi bắt đầu, cả hai phân xưởng đều chưa có sản phẩm. Sau khi kết thúc ngày làm việc, tất cả các sản phẩm đang làm dở đều được hoàn thành ngay.

Yêu cầu: Hãy tính số lượng sản phẩm tối đa mà nhà máy có thể hoàn thành trong một ngày.

Input:

Được cho bởi tệp bina4.inp:

• Dòng 1: Số nguyên ~T~ (~1 ≤ T ≤ 10^9~)
• Dòng 2: Số nguyên ~N~ (~1 ≤ N ≤ 100000~)
• Dòng 3: ~a_1, a_2, ..., a_N~ (~a_i ≤ 10^9~)
• Dòng 4: Số nguyên ~M~ (~1 ≤ M ≤ 100000~)
• Dòng 5: ~b_1, b_2, ..., b_M~ (~b_j ≤ 10^9~)

Output:

Được cho bởi tệp bina4.out:

• In ra một số nguyên là số lượng sản phẩm tối đa hoàn thành trong ngày.

Sample:

Input:

20
2
4 6
3
2 3 5

Output:

5