#include "Annalib.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
#define cq 38
void Anna( int n, long long x, int k, int p[] ){
mt19937 mt(2137);
vector<ll>v;
ll cur=0;
bool bl[n];
for(ll i=0;i<cq;i++){
v.pb(x%3);
x/=3;
}
reverse(v.begin(),v.end());
for(ll i=0;i<v.size();i++)v[i]=(v[i]+3-mt()%3)%3;
for(ll i=0;i<n;i++)bl[i]=0;
for(ll i=0;i<k;i++)bl[p[i]]=1;
for(ll i=0;i<cq;i++){
if(cur>=n)break;
if((bl[cur] && v[i]!=0) || (bl[cur+1] && v[i]!=1)){
Set(cur,0);
Set(cur+1,0);
cur+=2;
i--;
v[i]=(v[i]+mt()%3)%3;
}
else{
//cout<<cur<<" "<<flush;
v[i]=(v[i]+mt()%3)%3;
if(v[i]==0){
Set(cur,0);
Set(cur+1,1);
}
if(v[i]==1){
Set(cur,1);
Set(cur+1,0);
}
if(v[i]==2){
Set(cur,1);
Set(cur+1,1);
}
cur+=2;
}
}
for(ll i=cur;i<n;i++)Set(i,0);
}
long long Bruno( int n, int a[] ){
//cout<<"xd";
ll ans=0;
ll ak=0;
for(ll i=0;i<cq;i++){
if(ak>=n)break;
if(a[ak]==0 && a[ak+1]==0){
//cout<<ak<<" ";
i--;
ak+=2;
}
else{
//cout<<"xd"<<" ";
if(a[ak]==0)ans=ans*3+0;
else if(a[ak+1]==0)ans=ans*3+1;
else ans=ans*3+2;
ak+=2;
}
}
// cout<<ans<<" ";
return ans;
}
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000007
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
#define cq 38
long long Bruno( int n, int a[] ){
mt19937 mt(2137);
//cout<<"xd";
ll ans=0;
ll ak=0;
vector<ll>v;
ll x=0;
for(ll i=0;i<cq;i++){
if(a[ak]==0 && a[ak+1]==0){
//cout<<ak<<" ";
i--;
ak+=2;
x+=mt();
}
else{
//cout<<"xd"<<" ";
x+=mt();
if(a[ak]==0)v.pb(0);
else if(a[ak+1]==0)v.pb(1);
else v.pb(2);
v[i]=(v[i]+x%3)%3;
x=0;
ak+=2;
}
}
//for(ll i=0;i<v.size();i++)v[i]=(v[i]+mt()%3)%3;
for(ll i : v)ans=ans*3+i;
// cout<<ans<<" ";
return ans;
}
