#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
namespace{ //BEGIN MY_TEMPLATE
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple
#define tcT template<class T
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)
tcT> bool minimize(T& a, const T& b){
return (a > b ? a = b, 1 : 0);
}
tcT> bool maximize(T& a, const T& b){
return (a < b ? a = b, 1 : 0);
}
tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;
using ll = long long;
using db = double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
#define task "task"
void setIO(){
ios_base::sync_with_stdio(0); cin.tie(0);
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
}
tcT> void _print(const T& x){ cerr << x; }
void _print(const string& s){ cerr << '"' << s << '"'; }
void _print(const char* s){ cerr << '"' << s << '"'; }
void _print(char c){ cerr << '\'' << c << '\''; }
void _print(bool b){ cerr << (b ? "True" : "False"); }
tcT, class U> void _print(const pair<U, T>& p){
cerr << "("; _print(p.ff); cerr << ", "; _print(p.ss); cerr << ")";
}
tcT, class U, class V> void _print(const tuple<T, U, V>& t){
cerr << "("; _print(get<0>(t)); cerr << ", "; _print(get<1>(t)); cerr << ", "; _print(get<2>(t)); cerr << ")";
}
template<class it> void _print(it a, it b, string sep = ", "){
cerr << "{";
bool first = false;
for(it c = a; c != b; ++c){
if(first) cerr << sep;
_print(*c);
first = true;
}
cerr << "}";
}
tcT> void _print(const vector<T>& v){ _print(begin(v), end(v)); }
tcT> void _print(const set<T>& v){ _print(begin(v), end(v)); }
tcT> void _print(const multiset<T>& v){ _print(begin(v), end(v)); }
tcT, class U> void _print(const map<T, U>& v){ _print(begin(v), end(v)); }
void mainPrint(){ cerr << '\n'; }
tcT> void mainPrint(const T& a){ _print(a); cerr << '\n';}
tcT, class... U> void mainPrint(const T& a, const U&... b){
_print(a);
cerr << " | ";
mainPrint(b...);
}
#define debug(...) (cerr << "[" << __FILE__ << "|#" << __LINE__ << "]" << " [" << #__VA_ARGS__ << "] = ", mainPrint(__VA_ARGS__))
ll dp[50][50];
vi findKthSequence(ll K){
vi seq;
for(int i = 12; i >= 1; --i){
bool found = false;
F0R(j, 16){
if(dp[i][j] <= K){
K -= dp[i][j];
} else{
seq.pb(j);
found = true;
break;
}
}
assert(found);
}
return seq;
}
} //END MY_TEMPLATE
void encode(int N, int M[]){
if(N <= 15){
F0R(i, N){
//bit 0-1
F0R(bit, 8) if(M[i] >> bit & 1){
int num = i + (bit << 5);
send(num);
}
}
return;
}
//group the adjacent triplet into 1 big number P[j] = A[i] + 256 * A[i + 1] * 256^2 * A[i + 2]
//we will have ceil(N / 3) number of elements ~= 22 group (it takes 4 bits to declare the group)
//Note that the number of non-decreasing arrays of length 12 of integers in range [0, 16) is slightly more than 256^3
//so we map each number equal to the P[j]-th non-decreasing array (by lexicographical order)
//for each P[j], we send 12 integers
//so the total number of messages is 22 * 12 = 264 is much better tham 320
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
FOR(i, 1, 13){
F0R(j, 16){
F0R(k, j + 1){
dp[i][j] += dp[i - 1][k];
}
}
}
for(int s = 0; s < N; s += 3){
ll num = M[s] + 256 * (s + 1 < N ? M[s + 1] : 0) + 256ll * 256ll * (s + 2 < N ? M[s + 2] : 0);
int group = s / 3;
// cerr << "send pack of " << num << "\n";
vector<int> seq = findKthSequence(num);
// cerr << "encode : ";
// for(auto x : seq) cerr << x << ' ';
// cerr << '\n';
F0R(j, 12){
send(group + (seq[j] << 4));
}
}
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
namespace{ //BEGIN MY_TEMPLATE
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple
#define tcT template<class T
#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)
tcT> bool minimize(T& a, const T& b){
return (a > b ? a = b, 1 : 0);
}
tcT> bool maximize(T& a, const T& b){
return (a < b ? a = b, 1 : 0);
}
tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;
using ll = long long;
using db = double;
using ull = unsigned long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;
#define task "task"
void setIO(){
ios_base::sync_with_stdio(0); cin.tie(0);
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
}
tcT> void _print(const T& x){ cerr << x; }
void _print(const string& s){ cerr << '"' << s << '"'; }
void _print(const char* s){ cerr << '"' << s << '"'; }
void _print(char c){ cerr << '\'' << c << '\''; }
void _print(bool b){ cerr << (b ? "True" : "False"); }
tcT, class U> void _print(const pair<U, T>& p){
cerr << "("; _print(p.ff); cerr << ", "; _print(p.ss); cerr << ")";
}
tcT, class U, class V> void _print(const tuple<T, U, V>& t){
cerr << "("; _print(get<0>(t)); cerr << ", "; _print(get<1>(t)); cerr << ", "; _print(get<2>(t)); cerr << ")";
}
template<class it> void _print(it a, it b, string sep = ", "){
cerr << "{";
bool first = false;
for(it c = a; c != b; ++c){
if(first) cerr << sep;
_print(*c);
first = true;
}
cerr << "}";
}
tcT> void _print(const vector<T>& v){ _print(begin(v), end(v)); }
tcT> void _print(const set<T>& v){ _print(begin(v), end(v)); }
tcT> void _print(const multiset<T>& v){ _print(begin(v), end(v)); }
tcT, class U> void _print(const map<T, U>& v){ _print(begin(v), end(v)); }
void mainPrint(){ cerr << '\n'; }
tcT> void mainPrint(const T& a){ _print(a); cerr << '\n';}
tcT, class... U> void mainPrint(const T& a, const U&... b){
_print(a);
cerr << " | ";
mainPrint(b...);
}
#define debug(...) (cerr << "[" << __FILE__ << "|#" << __LINE__ << "]" << " [" << #__VA_ARGS__ << "] = ", mainPrint(__VA_ARGS__))
ll dp[50][50];
vi findKthSequence(ll K){
vi seq;
for(int i = 12; i >= 1; --i){
bool found = false;
F0R(j, 16){
if(dp[i][j] < K){
K -= dp[i][j];
} else{
seq.pb(j);
found = true;
break;
}
}
assert(found);
}
return seq;
}
ll countLowerLexi(vi seq){
ll ans = 0;
F0R(i, 12){
F0R(j, seq[i]) ans += dp[12 - i][j];
}
return ans;
}
} //END MY_TEMPLATE
void decode(int N, int L, int X[]){
if(N <= 15){
vector<int> ans(N);
F0R(i, L){
int num = X[i];
int first5 = num & ((1 << 5) - 1);
int last3 = num >> 5;
ans[first5] |= (1 << last3);
}
F0R(i, N) output(ans[i]);
return;
}
//group the adjacent triplet into 1 big number P[j] = A[i] + 256 * A[i + 1] * 256^2 * A[i + 2]
//we will have ceil(N / 3) number of elements ~= 22 group (it takes 4 bits to declare the group)
//Note that the number of non-decreasing arrays of length 12 of integers in range [0, 16) is slightly more than 256^3
//so we map each number equal to the P[j]-th non-decreasing array (by lexicographical order)
//for each P[j], we send 12 integers
//so the total number of messages is 22 * 12 = 264 is much better tham 320
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
FOR(i, 1, 13){
F0R(j, 16){
F0R(k, j + 1){
dp[i][j] += dp[i - 1][k];
}
}
}
vector<vi> groups(N);
F0R(i, L){
int g = X[i] & ((1 << 4) - 1);
int num = X[i] >> 4;
// cerr << g << ' ' << num << '\n';
groups[g].eb(num);
}
vi ans;
F0R(i, N){
if(groups[i].empty()) break;
sort(rall(groups[i]));
// cerr << i << " : " << sz(groups[i]) << '\n';
assert(sz(groups[i]) == 12);
// for(auto x : groups[i]) cerr << x << ' ';
// cerr << '\n';
ll num = countLowerLexi(groups[i]);
F0R(_, 3){
ans.eb(num % 256);
num /= 256;
}
}
// cerr << "decoder : ";
// F0R(i, N) cerr << ans[i] << " "; cerr << '\n';
F0R(i, N) output(ans[i]);
}
