#include "Annalib.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using i64 = long long;
using namespace std;
const i64 MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
bool backtrack(int i, i64 rem, vector<array<int, 2>>& crt, vector<i64>& sumAft, vector<int>& used) {
if(i == sz(crt)) return false;
if(rem > sumAft[i]) return false;
if(rem == crt[i][0]) {
used.push_back(crt[i][1]);
return true;
}
if(rem > crt[i][0]) {
if(backtrack(i+1, rem - crt[i][0], crt, sumAft, used)) {
used.push_back(crt[i][1]);
return true;
}
}
return backtrack(i+1, rem, crt, sumAft, used);
}
void Anna(int N, long long X, int K, int P[]) {
vector<bool> broken(N);
for(int i = 0; i < K; i++)
broken[P[i]] = 1;
mt19937 rng(42);
X ^= rng();
vector<array<int, 2>> crt[2];
vector<i64> sumAft[2];
for(int i = 0; i < N/2; i++) {
int val = rng() % MOD1;
if(!broken[i]) crt[0].push_back({val, i});
}
for(int i = N/2; i < N; i++) {
int val = rng() % MOD2;
if(!broken[i]) crt[1].push_back({val, i});
}
sort(all(crt[0])); reverse(all(crt[0]));
sort(all(crt[1])); reverse(all(crt[1]));
for(int i = 0; i < 2; i++) {
sumAft[i].resize(sz(crt[i]));
for(int j = sz(crt[i])-2; j >= 0; j--)
sumAft[i][j] = sumAft[i][j+1] + crt[i][j+1][0];
for(int j = 0; j < sz(crt[i]); j++)
sumAft[i][j] += crt[i][j][0];
}
vector<int> used[2];
for(int i = 0; i < 76; i++) {
if(backtrack(0, X % MOD1 + i * MOD1, crt[0], sumAft[0], used[0])) {
i = 76;
}
}
for(int i = 0; i < 76; i++) {
if(backtrack(0, X % MOD2 + i * MOD2, crt[1], sumAft[1], used[1])) {
i = 76;
}
}
vector<int> ans(N);
for(int i : used[0]) ans[i] = 1;
for(int i : used[1]) ans[i] = 1;
for(int i = 0; i < N; i++)
Set(i, ans[i]);
}
#include "Brunolib.h"
#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using i64 = long long;
using namespace std;
const i64 MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
using ll = __int128;
ll euclid(ll a, ll b, ll &x, ll &y) {
if (!b) return x = 1, y = 0, a;
ll d = euclid(b, a % b, y, x);
return y -= a/b * x, d;
}
ll crt(ll a, ll m, ll b, ll n) {
if (n > m) swap(a, b), swap(m, n);
ll x, y, g = euclid(m, n, x, y);
assert((a - b) % g == 0); // else no solution
x = (b - a) % n * x % n / g * m + a;
return x < 0 ? x + m*n/g : x;
}
long long Bruno( int N, int A[] ){
mt19937 rng(42);
i64 xored = rng(), a = 0, b = 0;
for(int i = 0; i < N/2; i++) {
i64 val = rng();
if(A[i]) a ^= val;
}
for(int i = N/2; i < N; i++) {
i64 val = rng();
if(A[i]) b ^= val;
}
return ((i64)crt(a, MOD1, b, MOD2)) ^ xored;
}
