#include <vector>
#include <iostream>

using namespace std;

const int N = 1e6 * 1.3;
int h[N]; // N=random[n..2n] 
int save(int x) { // O(1)
	int i = x % N; // hash-function
	while (h[i] != 0 && h[i] != x)
		i = (i + 1) % N; // линейное хеширование
	h[i] = x;
	return i;
}
// N*4*1.3 = N*5.2

// Фильтр-Блюма
const int M = N * 5;
const int K = 4; // K(M/N) ~= M/N * ln2
vector<bool> h2(M); // M битов
#define forn(i, n) for (int i = 0; i < (int)(n); i++)
const int A[] = {
	239017, 170239, 23917, 17239
};
void save2(int x) { // O(1)
	forn(j, K)
		h2[((int64_t)x * A[j]) % M] = 1;
}
bool we_have(int x) { // O(1)
	forn(j, K)
		if (!h2[((int64_t)x * A[j]) % M])
			return 0;
	return 1; // ~1%
}
// Фильтр-Блюма + (Хеш-Таблица снаружи)

int main() {
	
}