#include "message.h"
#include <bits/stdc++.h>
using namespace std;

using uint = unsigned int; using i64 = long long; using ui64 = unsigned long long; using i128 = __int128;
const int INF = 1e9; const i64 LLNF = 4e18;

template< class Tp > void chkmax( Tp &x, Tp y ) { x = max( x, y ); }
template< class Tp > void chkmin( Tp &x, Tp y ) { x = min( x, y ); }

int log( int x ) { return 31 - __builtin_clz( x ); }
int log( i64 x ) { return 63 - __builtin_clzll( x ); }

// 先把 <= 1024 长度通过补上 1000000, 变成 1025 长度的串. 现在只需要传输 1025 长度的串.
// 然后注意到有 66 * 16 - 1025 = 31 个可以另作他用的位置. 恰好是一次传输的长度.
// 所以设所有好的位置为 0 <= r[0] < ... <= r[15] <= 30. 则只需要传输 s[i] = ( r[i + 1] - r[i] ) % 31.
// 此时注意 sum s[i] = 31. 所以一样的, 在第 r[i] 个位置的前 s[i] 次传输中置为 000001. 总共使用了 31 个额外位置.
// 考虑 Bob 如何解密. 注意在第 u 列提取可以知道 u 的下一个好的位置 v. ( 在 u 是好位置的情况下 ).
// 所以现在连边 u -> v. 这就是一个 31 个点的基环树森林. 其中好的位置恰好构成一个长度为 16 的环. 这就很简单了.

void send_message( vector< bool > M, vector< bool > C ) {
	int S = ( int ) M.size( );
	M.emplace_back( 1 ); while( ( int ) M.size( ) < 1025 ) M.emplace_back( 0 );

	vector< int > r;
	for( int u = 0; u < 31; u ++ ) if( !C[u] ) r.emplace_back( u );
	assert( ( int ) r.size( ) == 16 );

	vector< int > s( 16 );
	for( int i = 0; i < 16; i ++ ) s[i] = ( r[( i + 1 ) % 16] - r[i] + 31 ) % 31;

	vector< vector< bool > > send( 66, vector< bool >( 31 ) ); vector< vector< bool > > used( 66, vector< bool >( 31 ) );
	for( int i = 0; i < 16; i ++ )
		for( int j = 0; j < s[i]; j ++ )
			send[j][r[i]] = ( j == s[i] - 1 ) ? ( 1 ) : ( 0 ), used[j][r[i]] = true;
	int cur = 0;
	for( int k = 0; k < 66; k ++ )
		for( int u = 0; u < 31; u ++ )
			if( !C[u] && !used[k][u] )
				send[k][u] = M[cur], used[k][u] = true, cur ++;

	for( int k = 0; k < 66; k ++ )
		send_packet( send[k] );
}

vector< bool > receive_message( vector< vector< bool > > R ) {
	vector< int > nxt( 31 );
	for( int u = 0; u < 31; u ++ ) {
		int k = 0;
		while( k < 66 && R[k][u] == 0 ) k ++;
		nxt[u] = ( u + k + 1 ) % 31;
	}

	vector< bool > C( 31 );
	for( int u = 0; u < 31; u ++ ) {
		vector< bool > vis( 31, false ); int t = u;
		while( !vis[t] ) vis[t] = true, t = nxt[t];
		if( t == u && count( vis.begin( ), vis.begin( ) + 31, true ) == 16 ) {
			for( int v = 0; v < 31; v ++ ) C[v] = !vis[v];
			break;
		}
	}

	vector< int > r;
	for( int u = 0; u < 31; u ++ ) if( !C[u] ) r.emplace_back( u );
	assert( ( int ) r.size( ) == 16 );

	vector< int > s( 16 );
	for( int i = 0; i < 16; i ++ ) s[i] = ( r[( i + 1 ) % 16] - r[i] + 31 ) % 31;

	vector< vector< bool > > used( 66, vector< bool >( 31 ) );
	for( int i = 0; i < 16; i ++ )
		for( int j = 0; j < s[i]; j ++ )
			used[j][i] = true;
	vector< bool > M;
	for( int k = 0; k < 66; k ++ )
		for( int u = 0; u < 31; u ++ )
			if( !C[u] && !used[k][u] )
				M.emplace_back( R[k][u] ), used[k][u] = true;

	while( !M.empty( ) && M.back( ) == 0 ) M.pop_back( ); M.pop_back( );

	return M;
}