Treeland có \(2N\) thành phố. Quy hoạch mạng lưới đường hiện có \(N\) đoạn đường thẳng, mỗi đoạn nối hai thành phố. Không có hai đoạn đường hiện có nào có điểm chung, kể cả đầu mút.

Hãy xây thêm \(N-1\) đoạn đường sao cho thỏa mãn tất cả các điều kiện sau:

1. Mỗi đoạn đường mới là một đoạn thẳng nối hai thành phố.
2. Nếu hai đoạn đường (cũ hoặc mới) có điểm chung, thì điểm chung đó phải là đầu mút của cả hai đoạn.
3. Mạng lưới đường kết nối tất cả các thành phố: giữa mọi cặp thành phố đều có một đường đi gồm các đoạn đường.

Nếu có nhiều cách xây dựng hợp lệ, bạn có thể in ra bất kỳ cách nào.

Dữ liệu vào

Dòng đầu gồm số nguyên \(N\), số đoạn đường hiện có.

Mỗi dòng trong \(N\) dòng tiếp theo gồm bốn số nguyên \(x_1,y_1,x_2,y_2\), mô tả một đoạn đường nối thành phố \((x_1,y_1)\) với thành phố \((x_2,y_2)\).

Dữ liệu ra

In \(N-1\) dòng. Mỗi dòng gồm bốn số nguyên \(x_1,y_1,x_2,y_2\), mô tả một đoạn đường mới nối thành phố \((x_1,y_1)\) với thành phố \((x_2,y_2)\).

Ví dụ

5
1 3 3 6
5 1 5 3
3 3 6 5
2 1 4 1
2 3 4 2

1 3 2 1
2 1 2 3
3 3 2 3
4 1 5 1

Hình dưới minh họa một mạng lưới đường hoàn chỉnh cho ví dụ.

Ràng buộc

• \(2\le N\le10^5\).
• \(-10^7\le x_i,y_i\le10^7\).

Phân nhóm

1. \(0\) điểm: Bộ dữ liệu mẫu.
2. \(15\) điểm: Mọi đoạn đường đầu vào đều thẳng đứng.
3. \(15\) điểm: Mọi cặp đoạn đường đầu vào đều song song.
4. \(15\) điểm: Mỗi đoạn đường đầu vào nằm ngang hoặc thẳng đứng.
5. \(15\) điểm: \(N\le10000\).
6. \(40\) điểm: Không có ràng buộc nào khác.