Trò chơi nối điểm dành cho một người được chuẩn bị như sau. Chọn hai số nguyên \(g,r\) lớn hơn \(2\). Vẽ bốn điểm ở bốn đỉnh của một hình vuông: hai đỉnh phía trên màu xanh lá, hai đỉnh phía dưới màu đỏ. Vẽ thêm các điểm xanh lá và đỏ ở bên trong hình vuông cho đến khi có tổng cộng \(g\) điểm xanh lá và \(r\) điểm đỏ. Các điểm phải được đặt sao cho không có ba điểm nào thẳng hàng, kể cả bốn điểm ở các đỉnh ban đầu.

Sau khi chuẩn bị xong, bạn có thể nối hai điểm bằng một đoạn thẳng nếu hai điểm cùng màu và đoạn thẳng đó không giao với bất kỳ đoạn nào đã vẽ, ngoại trừ tại các đầu mút chung.

Hai điểm \(u,v\) thuộc cùng một thành phần liên thông nếu có thể đi từ \(u\) đến \(v\) bằng các đoạn thẳng đã vẽ.

Bạn thắng khi nối tất cả các điểm xanh lá thành một thành phần liên thông bằng đúng \(g-1\) đoạn thẳng, đồng thời nối tất cả các điểm đỏ thành một thành phần liên thông khác bằng đúng \(r-1\) đoạn thẳng. Có thể chứng minh rằng nếu các điểm được đặt theo các điều kiện trên thì luôn tồn tại cách thắng.

Bạn được cho một bảng hình vuông có cạnh \(s\) và tọa độ nguyên \((x_i,y_i)\) của các điểm. Các điểm xanh lá được đánh số riêng từ \(1\) đến \(g\): điểm \(1\) ở góc trên trái \((0,s)\), điểm \(2\) ở góc trên phải \((s,s)\), còn các điểm bên trong mang số từ \(3\) đến \(g\) theo thứ tự bất kỳ. Tương tự, các điểm đỏ được đánh số riêng từ \(1\) đến \(r\): điểm \(1\) ở góc dưới trái \((0,0)\), điểm \(2\) ở góc dưới phải \((s,0)\), còn các điểm bên trong mang số từ \(3\) đến \(r\) theo thứ tự bất kỳ.

Hình minh họa một cách thắng: tất cả các điểm xanh lá thuộc cùng một thành phần liên thông, tất cả các điểm đỏ thuộc một thành phần khác. Không có ba điểm nào thẳng hàng và các đoạn thẳng không giao nhau, ngoại trừ tại đầu mút chung.

Hãy xác định \(g-1\) đoạn thẳng nối các điểm xanh lá và \(r-1\) đoạn thẳng nối các điểm đỏ để thắng trò chơi.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(g\).
• \(g\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i,y_i\) phân cách bởi một dấu cách, là tọa độ điểm xanh lá thứ \(i\), theo thứ tự từ \(1\) đến \(g\).
• Dòng thứ \(g+2\) chứa số nguyên \(r\).
• \(r\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i,y_i\) phân cách bởi một dấu cách, là tọa độ điểm đỏ thứ \(i\), theo thứ tự từ \(1\) đến \(r\).

Giá trị \(s\) không được cho trên một dòng riêng; các điểm ở bốn đỉnh được cho theo đúng quy ước trên.

Dữ liệu ra

Ghi ra đầu ra chuẩn đúng \((g-1)+(r-1)\) dòng, mỗi dòng mô tả một đoạn thẳng được vẽ.

Mỗi dòng chứa hai số nguyên và một ký tự, phân cách bởi dấu cách. Hai số nguyên là số hiệu hai đầu mút trong nhóm điểm cùng màu. Ký tự là g nếu nối hai điểm xanh lá, hoặc r nếu nối hai điểm đỏ.

Thứ tự liệt kê các đoạn thẳng và thứ tự hai đầu mút của mỗi đoạn đều không quan trọng. Các đoạn phải nối mỗi nhóm màu thành một thành phần liên thông và không được giao nhau, ngoại trừ tại các đầu mút chung.

Ràng buộc

• \(3\le g\le50\,000\).
• \(3\le r\le50\,000\).
• \(0 < s \le200\,000\,000\).
• Tất cả tọa độ là số nguyên; ngoài bốn đỉnh đã nêu, các điểm đều nằm bên trong hình vuông.
• Không có ba điểm nào thẳng hàng.

Chấm điểm

Trong các bộ dữ liệu có tổng cộng \(35\) điểm, đồng thời có \(3\le g\le20\) và \(3\le r\le20\).

Ví dụ

6
0 1000
1000 1000
203 601
449 212
620 837
708 537
8
0 0
1000 0
185 300
314 888
416 458
614 622
683 95
838 400

1 3 g
3 1 r
3 5 r
4 6 r
6 5 r
4 6 g
1 2 g
1 2 r
5 2 g
2 6 g
7 8 r
8 2 r

Nguồn

IOI 2006.