#include "Annalib.h"
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
using namespace std ;
ll pot[38] ;
void Anna( int N, long long X, int K, int P[] )
{
srand(36) ;
vector<int> vec(N,0) ;
iota(all(vec),0) ;
random_shuffle(all(vec)) ;
pot[0] = 1LL ;
for(int i = 1 ; i <= 37 ; i++ )
pot[i] = pot[i-1]*3LL ;
vector<bool> isBroken(N, false ) ;
for(int i = 0 ; i < K ; i++ ) isBroken[ P[i] ] = true ;
vector<int> base3( 38, 0 ) ;
for(int i = 37 ; i >= 0 ; i-- )
{
base3[i] = X/pot[i] ;
X -= pot[i] * base3[i] ;
}
//01 = 0
//10 = 1
//11 = 2
for(int i = 0, ptr = 0 ; i+1 < N ; i += 2 , ptr++ )
{
if( ptr > 37 )
{
Set(vec[i],0);
Set( vec[i+1] ,0) ;
continue ;
}
if(isBroken[ vec[i] ] && isBroken[ vec[i+1] ])
{
Set( vec[i] ,0) ;
Set( vec[i+1] ,0) ;
ptr-- ;
continue ;
}
if(isBroken[ vec[i] ])
{
Set(vec[i],0) ;
if( base3[ptr] == 0 )
Set(vec[i+1], 1) ;
else
{
ptr-- ;
Set(vec[i+1],0) ;
}
}
else if( isBroken[ vec[i+1] ] )
{
Set(vec[i+1],0) ;
if( base3[ptr] == 1 )
Set(vec[i],1) ;
else
{
ptr-- ;
Set(vec[i],0) ;
}
}
else
{
if( base3[ptr] == 0 )
{
Set(vec[i],0) ;
Set(vec[i+1],1) ;
}
else if(base3[ptr] == 1)
{
Set( vec[i] ,1) ;
Set( vec[i+1] ,0) ;
}
else
{
Set( vec[i] ,1) ;
Set( vec[i+1] ,1) ;
}
}
}
}
#include "Brunolib.h"
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define ll long long
using namespace std ;
ll pott[38] ;
long long Bruno( int N, int A[] )
{
srand(36) ;
vector<int> vec(N,0) ;
iota(all(vec),0) ;
random_shuffle(all(vec)) ;
pott[0] = 1LL ;
for(int i = 1 ; i <= 37 ; i++ )
pott[i] = pott[i-1]*3LL ;
ll tot = 0LL ;
for(int i = 0, ptr = 0 ; i+1 < N && ptr <= 37 ; i += 2 , ptr++ )
{
if( A[ vec[i] ] == 0 && A[ vec[i+1] ] == 0)
{
ptr-- ;
continue ;
}
if( A[ vec[i] ] == 1 && A[ vec[i+1] ] == 0 )
tot += pott[ptr] ;
else if( A[ vec[i] ] == 1 && A[ vec[i+1] ] == 1 )
tot += 2LL*pott[ptr] ;
}
return tot ;
}
