#include <bits/stdc++.h>
using namespace std;
long long collisions(vector<long long> x);
int hack() {
const int B = 100000; // threshold for "small" n
// -------------------------------------------------------------
// Phase 1: Detect small n (≤ B-1) using a consecutive set
// -------------------------------------------------------------
vector<long long> small(B);
for (int i = 0; i < B; ++i) small[i] = i + 1;
long long c_small = collisions(small);
if (c_small > 0) {
// n is between 2 and B-1
int lo = 2, hi = B - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
// Simulate collisions for n = mid using the same set
long long sim = 0;
vector<int> cnt(mid, 0);
for (long long x : small) {
int b = x % mid;
sim += cnt[b];
cnt[b]++;
}
if (sim > 0) hi = mid;
else lo = mid + 1;
}
// Verify and return (check a small window for safety)
for (int d = max(2, lo - 5); d <= min(B - 1, lo + 5); ++d) {
if (collisions({(long long)d, 2LL * d, 3LL * d}) == 3)
return d;
}
return -1; // should never be reached
}
// -------------------------------------------------------------
// Phase 2: n > 100000 – estimate via random set
// -------------------------------------------------------------
const int M = 50000; // size of random set
vector<long long> randSet;
mt19937 rng(12345); // fixed seed for reproducibility
set<long long> used;
while ((int)randSet.size() < M) {
long long x = uniform_int_distribution<long long>(1, 1000000000000000000LL)(rng);
if (used.insert(x).second)
randSet.push_back(x);
}
long long c_rand = collisions(randSet);
long long pairs = (long long)M * (M - 1) / 2;
long long n_est = pairs / max(1LL, c_rand); // maximum likelihood estimate
// Search around the estimate; we have enough budget for ~280k tests
const long long MAX_TESTS = (1000000 - B - M) / 3;
long long low = max(100001LL, n_est / 2);
long long high = min(1000000000LL, n_est * 2);
vector<long long> candidates;
for (long long d = low; d <= high && (long long)candidates.size() < MAX_TESTS; ++d)
candidates.push_back(d);
for (long long d : candidates) {
if (collisions({d, 2 * d, 3 * d}) == 3)
return d;
}
// Fallback: linear scan (should never be triggered with proper estimate)
for (long long d = 100001; ; ++d) {
if (collisions({d, 2 * d, 3 * d}) == 3)
return d;
}
return -1;
}
