Các điểm nối

“Các điểm nối” là một trò chơi rất nổi tiếng chỉ có một người chơi. Để bắt đầu chơi bạn hãy chọn ngẫu nhiên 2 số tự nhiên lớn hơn 1, ví dụ g và r. Bạn hãy vẽ trên giấy 4 điểm là đỉnh của một hình vuông, 2 đỉnh phía trên màu xanh và 2 đỉnh phía dưới màu đỏ. Sau đó bạn bắt đầu vẽ các điểm màu xanh hoặc đỏ bên trong hình vuông. Chú ý rằng không bao giờ được để cho 3 điểm bất kỳ (kể cả 4 điểm ban đầu) nằm trên một đường thẳng. Tiếp tục việc tạo các điểm như vậy cho đến khi số điểm màu xanh bằng g và số điểm màu đỏ bằng r.

Sau khi đã tạo xong các điểm thì bạn bắt đầu nối các cặp điểm bằng các đoạn thẳng. Bấy kỳ 2 điểm nào cũng có thể nối được đoạn thẳng với điều kiện:

·         Hai điểm được nối phải cùng màu, và

·         Đoạn thẳng nối hai điểm này không được giao với bất cứ đoạn thẳng nào đã được nối trước đó (trừ ra các điểm được nối).

Hai điểm u và v được gọi là cùng nằm trên một miền nếu tìm được một đường đi theo các đoạn thằng từ u đến v.

Bạn sẽ thắng nếu như bạn nối được tất cả g điểm màu xanh bởi g-1 đoạn thẳng và nối được tất cả r điểm màu đỏ bởi r-1 đoạn thẳng. Có thể chứng minh được rằng luôn tồn tại một cách chơi để bạn chiến thắng.

Cho trước s là kích thước của hình vuông với g điểm xanh và r điểm màu đỏ với các tọa độ nguyên cho bởi cặp số nguyên (xi, yi).

Các điểm màu xanh đánh số từ 1 đến g với điểm đỉnh trái (0,s) đánh số 1, điểm đỉnh phải (s,s) đánh số 2, các điểm bên trong hình vuông đánh số từ 3 đến g.

Các điểm đỏ đánh số từ 1 đến r với đỉnh dưới trái là (0,0) đánh số 1, đỉnh phải (s,0) đánh số 2, các điểm bên trong đánh số từ 3 đến r.

Hình dưới đây mô tả một cuộc chơi trong đó các điểm đã được nối xong, các điểm xanh nằm trong một miền, các điểm đỏ nằm trong một miền. Không có 3 điểm nào thẳng hàng và không có hai đoạn thẳng nào cắt nhau ngoại trừ các điểm đầu mút.

  Yêu cầu

Viết chương trình, cho trước tọa độ của g điểm xanh và r điểm đỏ, hãy xác định cách vẽ g-1 đoạn thẳng nối các điểm xanh và r-1 đoạn nối các điểm màu đỏ sao cho các điểm xanh nằm trong một miền và các điểm đỏ nằm trong một miền và không có hai đoạn nào cắt nhau.

Ràng buộc

3 ≤ g ≤ 50 000              Số lượng các điểm xanh

3 ≤ r  ≤ 50 000             Số lượng các điểm màu đỏ

0 < s ≤ 200 000 000

INPUT

Chương trình cần đọc dữ liệu từ tệp văn bản points.in có dạng sau:

OUTPUT

Chương trình cần đưa ra tệp kết quả points.out có dạng sau:

Cách chấm điểm

Với các Test có tổng điểm 35, mỗi Test sẽ có dữ liệu đầu vào thỏa mãn điều kiện:

3 ≤ g ≤ 20