Once, four Roman merchants met in a Roman mansion to discuss their trading plans. They faced the following problem: they traded the same type of goods, and if they traded in the same city, they would inevitably incur losses. They decided to divide up the cities between them where they would trade.

The map of Rome can be represented in this problem as a plane with certain points marked — the cities of the Roman Empire.

The merchants decided to choose a certain dividing point (𝑥0,𝑦0). Then, in a city with coordinates (𝑥𝑖,𝑦𝑖),

the first merchant sells goods if 𝑥0≤𝑥𝑖 and 𝑦0≤𝑦𝑖;
the second merchant sells goods if 𝑥0>𝑥𝑖 and 𝑦0≤𝑦𝑖;
the third merchant sells goods if 𝑥0≤𝑥𝑖 and 𝑦0>𝑦𝑖;
the fourth merchant sells goods if 𝑥0>𝑥𝑖 and 𝑦0>𝑦𝑖.
The merchants want to choose (𝑥0,𝑦0) in such a way as to maximize the smallest number of cities that any of them gets (i. e., as fair as possible). Please find such a point for them.

Input
Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤104). The description of the test cases follows.

The first line of each test case contains a single integer 𝑛 (4≤𝑛≤2⋅105) — the number of cities on the map.

Each of the next 𝑛 lines contains two integers 𝑥𝑖,𝑦𝑖 (−109≤𝑥𝑖,𝑦𝑖≤109) — the coordinates of the cities.

Note that some points may coincide. This is because some cities may be so close that they cannot be distinguished on the map at the given scale.

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 2⋅105.

Output
For each test case, in the first line, print a single integer 𝑘 (0≤𝑘≤𝑛4) — the maximum possible number of cities that each merchant can get at a minimum.

In the second line, print two integers 𝑥0 and 𝑦0 (|𝑥0|,|𝑦0|≤109) — the coordinates of the dividing point. If there are multiple suitable points, print any of them.

Example
inputCopy
4
4
1 1
1 2
2 1
2 2
4
0 0
0 0
0 0
0 0
8
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1
-2 1
-1 2
7
1 1
1 2
1 3
1 4
2 1
3 1
4 1
outputCopy
1
2 2
0
0 0
2
1 0
0
0 0. Please use segment tree to optimize this code: #include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

void solve() {
  int n;
  cin >> n;
  vector<pair<int, int>> cities(n);
  for(auto &p : cities) cin >> p.first >> p.second;
  
  vector<int> xs, ys;
  for(auto &p : cities) {
    xs.push_back(p.first);
    ys.push_back(p.second);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  sort(ys.begin(), ys.end());
  ys.erase(unique(ys.begin(), ys.end()), ys.end());
  
  
  auto is_possible = [&](int k, int &best_x0, int &best_y0) -> bool {
    if(4 * k > n) return false;
    
    for(int i = 0; i <= (int)xs.size(); ++i) {
      
      int x0 = (i < xs.size()) ? xs[i] : xs.back() + 1;
      
      for(int j = 0; j <= (int)ys.size(); ++j) {
        int y0 = (j < ys.size()) ? ys[j] : ys.back() + 1;
        
        int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0;
        for(auto &p : cities) {
          if(p.first >= x0 && p.second >= y0) cnt1++;
          else if(p.first < x0 && p.second >= y0) cnt2++;
          else if(p.first >= x0 && p.second < y0) cnt3++;
          else cnt4++;
        }
        if(min({cnt1, cnt2, cnt3, cnt4}) >= k) {
          best_x0 = x0;
          best_y0 = y0;
          return true;
        }
      }
    }
    return false;
  };
  
  int left = 0, right = n / 4;
  int final_k = 0, final_x0 = 0, final_y0 = 0;
  while(left <= right) {
    int mid = left + (right - left) / 2;
    int x0, y0;
    if(is_possible(mid, x0, y0)) {
      final_k = mid;
      final_x0 = x0;
      final_y0 = y0;
      left = mid + 1;
    }
    else {
      right = mid - 1;
    }
  }
  
  cout << final_k << "\n" << final_x0 << " " << final_y0 << "\n";
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);

  int t; cin >> t;
  while (t--) solve();

}