Lãnh thổ của quốc gia Alpha là một hình vuông có kích thước mỗi cạnh là ~2 \times 10^9~ đơn vị, được chia thành ~4 \times 10^{18}~ ô từ ~2 \times 10^9~ hàng và ~2 \times 10^9~ cột, mỗi hàng và cột đều có kích thước là 1 đơn vị. Các hàng được đánh số từ 1 tới ~2 \times 10^9~ từ dưới lên trên, còn các cột cũng được đánh số từ 1 tới ~2 \times 10^9~ từ trái sang phải. Hai ô đất khác nhau bất kỳ được gọi là kết nối với nhau nếu chúng chung một cạnh hoặc chung một đỉnh với nhau.

Sơn có ~n~ quyển sổ đỏ nông nghiệp, quyển thứ ~i~ ứng với mảnh đất thứ ~i~ có kích thước ~r_i \times c_i~ và có đỉnh trái dưới là ~(x_i, y_i)~. Do khả năng quản lý đất chưa được tốt, một số quyển sổ đỏ có thể bị trùng lặp các ô đất lên nhau. May mắn là các quyển sổ đỏ của Sơn có thể có trùng lặp ở vài ô đất, nhưng không có quyển sổ đỏ của người nào khác trùng lặp lên các ô đất của Sơn.

Để bảo vệ các mảnh đất của mình, Sơn quyết định:

• Hai mảnh đất thứ ~i~ và thứ ~j~ của Sơn được gọi là kết nối với nhau, nếu tồn tại một ô ở mảnh ~i~ và một ô ở mảnh ~j~ kết nối với nhau.
• Những mảnh đất đôi một kết nối với nhau tạo thành một trang trại. Mỗi trang trại sẽ trồng một loại cây ăn trái khác nhau.
• Xây dựng các hàng rào xung quanh các trang trại của mình bằng cách ghép các tấm hàng rào có chiều dài 1m liên tiếp nhau dọc theo tất cả các cạnh nằm giữa các ô thuộc các mảnh đất của Sơn và các ô không thuộc sở hữu của Sơn. Ở đây ta coi kích thước các hàng rào là không đáng kể. Nếu có một ô của mảnh đất nằm ở biên giới quốc gia (tức tọa độ hàng hoặc cột có giá trị là 1 hoặc ~2 \times 10^9~) thì Sơn vẫn phải xây hàng rào trên ô này.

Để lên dự toán chi phí, Sơn muốn biết:

• Trang trại nào mua nhiều tấm hàng rào nhất?
• Tổng số tấm hàng rào cần mua để có thể rào toàn bộ các trang trại là bao nhiêu?

Yêu cầu: Hãy tính số tấm hàng rào của trang trại lớn nhất và tổng số tấm hàng rào cần dùng.

Input

• Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 10^5~) là số quyển sổ đỏ mà Sơn đang có.
• Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa 4 số nguyên ~x_i, y_i, r_i, c_i~ (~1 \le x_i, y_i, r_i, c_i \le 10^9~) thể hiện vị trí và kích thước của mảnh đất thứ ~i~ ứng với sổ đỏ thứ ~i~.

Output

• In ra một dòng duy nhất chứa hai số, lần lượt là số tấm cần dùng để rào trang trại cần nhiều hàng rào nhất, và tổng số tấm hàng rào cần dùng để rào toàn bộ các trang trại của Sơn.

Sample Input 1

6
7 4 1 3
1 1 2 2
8 3 1 2
7 1 2 3
3 3 2 1
7 2 3 1

Sample Output 1

18 32

Có ~n~ bạn sinh viên trong Câu lạc bộ Khoa học (CLB), trong đó có ~m~ cặp bạn bè quen nhau. Hải - chủ nhiệm CLB muốn thành lập một số nhóm, sao cho trong mỗi nhóm không chứa hai bạn bất kì không quen nhau. Ngoài ra, Hải cũng muốn đảm bảo mỗi một cặp bạn trong số ~m~ cặp bạn quen nhau này đều thuộc về ít nhất một nhóm chung với nhau. Vì những yêu cầu đặc thù đó, có thể có những bạn sinh viên thuộc vào nhiều nhóm khác nhau.

Yêu cầu: Hãy phân nhóm các bạn sinh viên sao cho số lượng nhóm là ít nhất có thể. Đây là bài toán Output Only.

Input

Thí sinh tải đầu vào tại đường dẫn: https://lqdoj.edu.vn/media/uploads/olp5scpartition_PmmCALo.zip Mỗi file input chứa:

• Dòng đầu chứa hai số nguyên ~n, m~ (~1 \le n \le 1000, 1 \le m \le \frac{n(n-1)}{2}~).
• Mỗi dòng trong số ~m~ dòng tiếp theo chứa hai số nguyên ~u, v~ (~1 \le u, v \le n~), nghĩa là ~u, v~ là bạn bè với nhau.

Output

Với mỗi file input, nộp file output tương ứng:

• Dòng đầu chứa số ~k~ là số nhóm được lập ra.
• Dòng thứ ~i~ trong số ~k~ dòng tiếp theo ghi ra số ~c_i~ là số lượng bạn trong nhóm ~i~, tiếp theo sau là ~c_i~ số tương ứng là chỉ số của các bạn sinh viên trong nhóm này.
• Output phải đảm bảo tổng số thành viên trong các nhóm không quá 10 lần số cặp bạn bè trong Input, nghĩa là ~\sum c_i \le 10 \times m~.

Sample Input 1

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

Sample Output 1

2
3 2 3 4
3 1 2 3