#include "hack.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using lld = long long int;
int hack() {
lld l = 500000002;
lld r = 1000000001;
lld sum = 0;
while (l + 1 < r) {
for (lld i = 0; i < (lld)log2(r - l + 1); i++) {
lld sq = ceil(sqrt((r - l) / 2));
vector<lld> x(sq * 2);
for (lld j = 0; j < sq; j++) {
x[j] = j + 1;
}
for (lld j = 0; j < sq; j++) {
x[sq + j] = l + (sq) * (j + 1) - 1;
}
lld col = collisions(x);
if (col) {
r = x[sq * 2 - 1];
}
else l = x[sq * 2 - 1] + 1;
sum += sq * 2;
}
}
lld col;
if (collisions({ 1, l })) col = l - 1;
else col = l;
for (lld i = 2; i <= sqrt(col); i++) {
if (col % i == 0) {
if (collisions({ 1, i + 1 })) return i;
}
}
for (lld i = sqrt(col); i >= 2; i--) {
if (col % i == 0) {
if (collisions({ 1, (col / i) + 1 })) return col / i;
}
}
return col;
}
