POINT - Khoảng cách mong manh

Giới hạn
  • Thời gian: 0.43s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Cho N điểm phân biệt trên mặt phẳng toạ độ . Toạ độ của điểm i là ( Xi , Yi ) trong đó Xi , Yi là các số nguyên ( -10000 ≤ Xi , Yi ≤ 10000 ) .
Ta định nghĩa khoảng cách giữa 2 điểm (X1,Y1) , (X2,Y2) là khoảng cách Manhattan được tính = | X1 – X2 | + | Y1 – Y2 | .
Hàm Q(X,Y) := | X – X1 | + | X – X2 | + … + | X – Xn | + | Y – Y1 | + … |Y – Yn | .
( Trong đó X , Y là 2 số nguyên thoả mãn -10000 ≤ X , Y ≤ 10000 và Xi ≠ X hoặc Yi ≠ Y với mọi i = 1 .. n ) .
Hãy tìm tập tất cả các điểm nguyên (X,Y) để hàm Q(X,Y) có giá trị nhỏ nhất .

Input

Dòng 1 : số nguyên dương T là số bộ test ( T ≤ 20 ) .
Các nhóm dòng sau mô tả 1 bộ test . 1 bộ test sẽ có format như sau :
Dòng 1 : số nguyên dương N ( N ≤ 10000 ) .
N dòng tiếp theo , dòng thứ i gồm 2 số nguyên là toạ độ của điểm thứ i .

Output

Với mỗi bộ test ghi 1 dòng gồm 2 số nguyên dương S , K tương ứng là giá trị nhỏ nhất của hàm Q(X,Y) và số lượng điểm thoả mãn yêu cầu .

Example

Input:
1
2
0 1
1 0

Output:
2 2


  • Người up: hard7771988
  • Nguồn bài: Dựa theo 1 bài dễ hơn của USACO