#include "hack.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long INF = 1e9;
int ans(int l, int r) {
// Binary search untuk menemukan nilai minimum yang memicu collision
while (l < r) {
int m = (l + r) >> 1;
int c = sqrtl(m - l + 1);
vector<int> q;
// Tambahkan titik awal
for (int i = 1; i <= c; ++i) {
q.push_back(i);
}
// Tambahkan sampel dari l + c hingga m dengan step c
for (int x = l + c; x <= m; x += c) {
q.push_back(x);
}
// Pastikan m+1 dicoba jika relevan
if (m + 1 > c) {
q.push_back(m + 1);
}
// Cek collision
if (collisions(q)) {
r = m;
} else {
l = m + 1;
}
}
// Persiapan sieve hingga sqrt(l) untuk mendapatkan daftar prima
int limit = sqrtl(l);
vector<bool> is_prime(limit + 1, true);
is_prime[0] = is_prime[1] = false;
vector<int> primes;
for (int i = 2; i <= limit; ++i) {
if (is_prime[i]) {
primes.push_back(i);
if ((long long)i * i <= limit) {
for (int j = i * i; j <= limit; j += i) {
is_prime[j] = false;
}
}
}
}
// Memurnikan hasil dengan membagi faktor prima selama memenuhi collision
int prev = -1;
while (l != prev) {
prev = l;
for (int p : primes) {
if (l % p == 0) {
if (collisions({1, l / p + 1})) {
l /= p;
break;
}
}
}
}
return l;
}
signed hack() {
return ans(INF / 2, INF);
}
