Một vùng đất hình chữ nhật có thể xem như một lưới ô vuông tạo bởi n dòng và m cột. Trên vùng đất đó người ta xây dựng h đường ngang và v đường dọc. Các đường này là những đường thẳng đi qua biên của các ô trên cùng dòng hay cùng cột, bắt đầu và kết thúc trên biên của vùng đất. Các đường ngang được đánh số từ 1 đến n + 1 từ trên xuống dưới và các đường dọc được đánh số từ 1 đến m + 1 từ trái sang phải.
Để lên kế hoạch cho một dự án xây dựng nhà ở, người ta khảo sát vùng đất để mỗi ngôi nhà có thể xây dựng trên một mảnh đất hình vuông có diện tích k \times k. Tất cả các hình vuông dựng nhà đều có diện tích bằng nhau, không phủ lên nhau, không phủ lên các con đường. Chúng có thể giáp hoặc không giáp với các con đường. Không có ô đất nào được để trống. Để tiện tính toán chúng ta bỏ qua độ rộng của các con đường.
Yêu cầu: Hãy tìm những giá trị k thỏa mãn điều kiện xây dựng nhà cho dự án.
Dữ liệu vào từ tệp văn bản CAU2.INP
gồm:
- Dòng đầu tiên chứa bốn số nguyên n, m, h, v (1 \leq n, m \leq 10^{18}, 0 \leq h, v \leq 2 \times 10^5);
- Nếu h > 0 thì dòng tiếp theo chứa h số nguyên h_i, i = 1, 2, ..., h (1 \leq h_i \leq n + 1, 1 \leq i \leq h) là chỉ số các con đường ngang, tương tự nếu v > 0 thì dòng tiếp theo chứa các v_i, i = 1, 2, ..., v (1 \leq v_i \leq m + 1, 1 \leq i \leq v) là chỉ số thuộc đường dọc. Không có trường hợp h = 0 và v > 0 hoặc h > 0 và v = 0. các $h_i và v_i có thể trùng nhau.
Các số trên một dòng cách nhau dấu cách.
Kết quả ghi ra tệp văn bản CAU2.OUT
gồm:
- Dòng đầu ghi một số là số giá trị k tìm được;
- Dòng thứ hai là các giá trị k tìm được, các số ghi cách nhau dấu cách và theo thứ tự tăng.
Chấm điểm:
- 50% số điểm có h = 0 và v = 0;
- 50% số điểm còn lại có h > 0 và v > 0. Không có hình chữ nhật nào được tạo ra bởi việc chia của các con đường này có kích thước cạnh lớn hơn 10^{14}.
Ví dụ:
Example 1
CAU2.INP
2 4 0 0
CAU2.OUT
2
1 2
Example 2
CAU2.INP
6 8 1 1
3
3
CAU2.OUT
2
1 2
Example 3
CAU2.INP
44 36 3 6
25 33 9
9 37 9 21 29 9
CAU2.OUT
3
1 2 4
Giải thích ví dụ 2: n = 6, m = 8, h = 1, v = 1 và h_1 = 3, v_1 = 3.
Comments