//Expected to be O(2N) switches
#include "doll.h"
#include <bits/stdc++.h>
#define debug printf
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
const int inf=1e9+10 ;
const int MAXN = 2e5+10;
using namespace std ;
int n , m , qtd ;
int triggers[MAXN*2] ;
// -------------------------
struct node
{
int id , l , r , gate ;
} ;
node v[MAXN*4] ;
int mid(int l , int r ) { return (l+r)/2 ; }
int createTree(int pos, int l , int r , int cur )
{
if(l==r) return cur - 1 ;
int last = createTree( pos*2, l , mid(l,r) , cur+1 ) ;
last = createTree(pos*2+1, mid(l,r)+1 , r , last+1 ) ;
v[pos].id = -cur ;
v[pos].gate = 0 ;
//printf("%d %d has become %d\n" , l , r , cur ) ;
return last ;
}
void simula(int pos, int l, int r , int cur )
{
if(l==r)
{
v[pos].id = triggers[cur] ;
if( ++cur <= qtd) simula(1 , 1 , qtd , cur ) ;
return ;
}
int nxt = pos*2 ;
pii p = mk( l , mid(l,r) ) ;
if( v[pos].gate == 1 )
{
nxt ++ ;
p = mk(mid(l,r)+1, r) ;
}
v[pos].gate = !v[pos].gate ;
simula(nxt , p.ff , p.ss , cur ) ;
v[pos].l =v[pos*2].id ;
v[pos].r = v[pos*2+1].id ;
}
void print(int pos, int l, int r)
{
printf("%d %d -> %d %d\n" , l , r , v[pos].l , v[pos].r ) ;
if(l==r) return ;
print(pos*2, l , mid(l,r)) ;
print(pos*2+1, mid(l,r)+1, r) ;
}
void create_circuit(int M, vector<int> A)
{
m = M ;
n = A.size() ;
lp(i,1,n+1) triggers[i] = A[i-1] ;
++ n ;
for(int i = 0 ; i <= 21 ; i++ )
if( (1<<i) >= n )
{ qtd = (1<<i) ; break ; }
lp(i , n , qtd ) triggers[i] = -1 ;
triggers[qtd] = 0 ;
vector<int> c(m+1) ;
lp(i,0,m+1) c[i] = -1 ;
createTree( 1 , 1 , qtd , 1 ) ;
simula(1 , 1 , qtd , 1 ) ;
//print(1,1,qtd) ;
vector<int> x(qtd-1) , y(qtd-1) ;
lp(i,1,qtd)
{
int curId = -v[i].id ;
x[curId-1] = v[i].l ;
y[curId-1] = v[i].r ;
}
/*printf("%d switches\n" , qtd-1) ;
lp(i,1,qtd) printf("%d %d\n" , x[i-1] , y[i-1]); */
answer(c , x , y ) ;
}
