#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define mxn 555
//#define send(x) cout<<x<<" ";
#include "encoder.h"
#include "encoderlib.h"
using namespace std;
const int Dig = 10;
struct bigint {
deque<int> num;
int sign = 1;
//constructor
bigint() {
}
bigint(long long x) {
num.clear();
if (x < 0)
sign = -1, x = -x;
if (x == 0)
num.push_back(x);
while (x > 0) {
num.push_back(x % Dig);
x /= Dig;
}
}
bigint(int x) {
num.clear();
if (x < 0)
sign = -1, x = -x;
if (x == 0)
num.push_back(x);
while (x > 0) {
num.push_back(x % Dig);
x /= Dig;
}
}
bigint(const bigint &x) {
sign = x.sign;
num = x.num;
}
// change to int
friend int BtoI(const bigint &x) {
int res = 0, t = 1;
for (int i = 0; i < x.num.size(); i++)
res += t * x.num[i];
return res;
}
//absolut
friend bigint abs(const bigint &x) {
bigint res = x;
res.sign = 1;
return res;
}
//clear 0
void clr() {
while (!num.empty() and !num.back())
num.pop_back();
}
//normalize
void normalize() {
(*this).clr();
int carry = 0;
for (int i = 0; i < num.size(); i++) {
int t = num[i] + carry;
if (t < 0) {
t += Dig;
carry = -1;
num[i] = t;
}
else {
num[i] = t % Dig;
carry = t / Dig;
}
}
if (carry > 0)
num.push_back(carry);
if (carry < 0) {
sign *= -1;
num.push_back(-carry);
}
(*this).clr();
if (num.empty())
sign = 1;
}
//is 0
bool isZero() {
(*this).normalize();
return num.empty();
}
//compare operators
bool operator<(const bigint &x) const {
bigint a = (*this);
bigint b = x;
a.normalize();
b.normalize();
if (a.sign != b.sign)
return a.sign < b.sign;
bool res = false, flag = false;
if (a.num.size() != b.num.size()) {
res = (a.num.size() < b.num.size());
flag = true;
}
else {
for (int i = a.num.size() - 1; i >= 0; i--)
if (a.num[i] != b.num[i]) {
flag = true;
res = (a.num[i] < b.num[i]);
break;
}
}
if (!flag)
return false;
if (sign == -1)
return !res;
return res;
}
bool operator==(const bigint &x) const {
bigint a = (*this);
bigint b = x;
a.normalize();
b.normalize();
if (a.sign == b.sign and a.num.size() == b.num.size()) {
bool res = true;
for (int i = 0; i < a.num.size() and res; i++)
if (a.num[i] != b.num[i])
res = false;
return res;
}
else
return false;
}
bool operator<=(const bigint &x) const {
return (((*this) < x) or ((*this) == x));
}
bool operator>(const bigint &x) const {
return (!((*this) <= x));
}
bool operator>=(const bigint &x) const {
return (!((*this) < x));
}
bool operator!=(const bigint &x) const {
return (!((*this) == x));
}
friend bigint max(bigint &x, bigint &y) {
return (x > y? x: y);
}
friend bigint min(bigint &x, bigint &y) {
return (x < y? x: y);
}
//math operators
bigint operator+(const bigint &x) const {
if (sign == x.sign) {
bigint res;
res.sign = sign;
for (int i = 0; i < max(x.num.size(), num.size()); i++) {
int t = (i >= num.size()? 0: num[i]) + (i >= x.num.size()? 0: x.num[i]);
res.num.push_back(t);
}
res.normalize();
return res;
}
if (sign == -1)
return x - abs(*this);
else
return (*this) - abs(x);
}
bigint operator-(const bigint &x) const {
if (sign == x.sign) {
bigint res, a = abs(*this), b = abs(x);
a.clr();
b.clr();
if (a == b) {
res = 0;
return res;
}
if (b < a) {
for (int i = 0; i < a.num.size(); i++) {
int t = a.num[i] - (i >= b.num.size()? 0: b.num[i]);
res.num.push_back(t);
}
res.normalize();
}
else {
for (int i = 0; i < b.num.size(); i++) {
int t = b.num[i] - (i >= a.num.size()? 0: a.num[i]);
res.num.push_back(t);
}
res.normalize();
res.sign *= -1;
}
if (sign == -1)
res.sign *= -1;
return res;
}
if (sign == -1) {
bigint res = abs(*this) + x;
res.sign *= -1;
return res;
}
else
return (*this) + abs(x);
}
void operator+=(const bigint &x) {
(*this) = (*this) + x;
}
void operator-=(const bigint &x) {
(*this) = (*this) - x;
}
void operator++() {
(*this) += 1;
}
bigint operator++(int) {
bigint res;
++(*this);
return res;
}
void operator--() {
(*this) -= 1;
}
bigint operator--(int) {
bigint res;
--(*this);
return res;
}
bigint operator*(const bigint &x) const {
bigint res;
bigint a = (*this), b = x;
if (a.isZero() or b.isZero())
return 0;
a.clr();
b.clr();
for (int i = 0; i < b.num.size(); i++) {
bigint t;
for (int j = 1; j <= i; j++)
t.num.push_back(0);
for (int j = 0; j < a.num.size(); j++)
t.num.push_back(a.num[j] * b.num[i]);
t.normalize();
res += t;
}
res.normalize();
res.sign = a.sign * b.sign;
return res;
}
void operator*=(const bigint &x) {
(*this) = (*this) * x;
}
friend pair<bigint, bigint> dmod(const bigint &x, const bigint &y) {
bigint res, a = abs(x), b = abs(y), carry;
res.sign = y.sign * x.sign;
a.clr();
b.clr();
if (b.isZero())
return {-1, -1};
if (a < b) {
return {0, x};
}
int cnt = a.num.size() - 1;
for (int i = a.num.size() - 1; carry < b; i--) {
carry.num.push_front(a.num[i]);
cnt = i - 1;
}
for (int i = 1; i <= 10; i++) {
bigint t = b * i;
if (t > carry) {
res.num.push_front(i - 1);
t -= b;
carry -= t;
break;
}
}
for (int i = cnt; i >= 0; i--) {
carry.num.push_front(a.num[i]);
carry.normalize();
if (carry >= b) {
for (int j = 1; j <= 10; j++) {
bigint t = b * j;
if (t > carry) {
res.num.push_front(j - 1);
t -= b;
carry -= t;
break;
}
}
}
else {
res.num.push_front(0);
}
}
res.normalize();
if (res.sign == -1)
carry = y - x;
return {res, carry};
}
bigint operator/(const bigint &x) const {
pair<bigint, bigint> res = dmod((*this), x);
return res.first;
}
void operator/=(const bigint &x) {
(*this) = (*this) / x;
}
bigint operator%(const bigint &x) const {
pair<bigint, bigint> res = dmod((*this), x);
return res.second;
}
void operator%=(const bigint &x) {
(*this) = (*this) % x;
}
friend bigint pow(const bigint &x, const bigint &y) {
bigint tmp = y;
if (tmp.isZero())
return 1;
bigint res = 1, t = y, a = x;
pair<bigint, bigint> dm;
while (t > 0) {
if ((t % 2) == 1)
res = res * a;
a *= a;
t /= 2;
}
return res;
}
friend bigint gcd(bigint x, bigint y) {
return (y.isZero()? x: gcd(y, x % y));
}
friend bigint lcm(const bigint &x, const bigint &y) {
return (x * y) / gcd(x, y);
}
friend bigint sqrt(const bigint &x) {
if (x.sign == -1)
return -1;
bigint carry, res, lef;
deque<pair<int, int>> t;
for (int i = 0; i < x.num.size(); i += 2) {
if (i + 1 == x.num.size())
t.push_front({x.num[i], 1});
else
t.push_front({x.num[i] + x.num[i + 1] * 10, 2});
}
for (int i = 0; i < t.size(); i++) {
if (t[i].second == 1)
carry.num.push_front(t[i].first);
else
carry.num.push_front(t[i].first / 10), carry.num.push_front(t[i].first % 10);
carry.normalize();
lef.num.push_front(0);
for (int i = 1; i <= 10; i++) {
lef.num[0] = i;
bigint tmp = (lef) * i;
if (tmp > carry) {
lef.num[0] = i - 1;
tmp = lef * (i - 1);
carry -= tmp;
lef += (i - 1);
res.num.push_front(i - 1);
break;
}
}
}
res.normalize();
return res;
}
//string to bigint and bigint to string
void toBig(string &s) {
if (s[0] == '-') {
sign = -1;
s = s.substr(1);
}
else
sign = 1;
reverse(s.begin(), s.end());
num.clear();
for (int i = (s[0] == '-'); i < s.size(); i += Dig / 10) {
string sp;
for (int j = i; j < i + (Dig / 10); j++)
sp += s[j];
long long t = stol(sp);
num.push_back(t);
}
}
friend string to_string(const bigint &x) {
string res;
if (x.num.empty()) {
res += '0';
return res;
}
if (x.sign == -1)
res += '-';
for (int i = x.num.size() - 1; i >= 0; i--) {
string t = to_string(x.num[i]);
reverse(t.begin(), t.end());
res += t;
}
return res;
}
//change base
friend bigint change_base(const bigint &a, const int y, const int x) {
if (y == x)
return a;
bigint res, t = change_base_rev(a, y, 10);
t.normalize();
while (t > 0) {
res.num.push_back(BtoI(t % x));
t /= x;
}
return res;
}
friend bigint change_base_rev(const bigint &a, const int y, const int x) {
if (y == x)
return a;
if (x == 10) {
bigint res, t = 1, b = a;
b.clr();
for (int i = 0; i < b.num.size(); i++)
res += t * b.num[i], t *= y;
return res;
}
bigint t = change_base_rev(a, y, 10);
return change_base(t, 10, x);
}
friend bigint CB(const bigint &a, int y, int x) {
if (x > y)
return change_base_rev(a, y, x);
return change_base(a, y, x);
}
//bitwise operator
bigint operator^(const bigint &x) const {
bigint res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
int d1 = 0, d2 = 0;
if (i < a.num.size())
d1 = a.num[i];
if (i < b.num.size())
d2 = b.num[i];
res.num.push_back(d1 ^ d2);
}
res.clr();
res = change_base_rev(res, 2, 10);
res.normalize();
return res;
}
bigint operator&(const bigint &x) const {
bigint res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
int d1 = 0, d2 = 0;
if (i < a.num.size())
d1 = a.num[i];
if (i < b.num.size())
d2 = b.num[i];
res.num.push_back(d1 & d2);
}
res.clr();
res = change_base_rev(res, 2, 10);
res.normalize();
return res;
}
bigint operator|(const bigint &x) const {
bigint res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
int d1 = 0, d2 = 0;
if (i < a.num.size())
d1 = a.num[i];
if (i < b.num.size())
d2 = b.num[i];
res.num.push_back(d1 | d2);
}
res.clr();
res = change_base_rev(res, 2, 10);
res.normalize();
return res;
}
void operator^=(const bigint &x) {
(*this) = (*this) ^ x;
}
void operator&=(const bigint &x) {
(*this) = (*this) & x;
}
void operator|=(const bigint &x) {
(*this) = (*this) | x;
}
bigint operator<<(const bigint &x) {
bigint res = change_base((*this), 10, 2);
for (bigint i = 0; i < x; i++)
res.num.push_front(0);
res = change_base_rev(res, 2, 10);
res.normalize();
return res;
}
bigint operator>>(const bigint &x) {
bigint res = change_base((*this), 10, 2);
bigint t = (int)res.num.size();
for (bigint i = 0; i < min(x, t); i++)
res.num.pop_front();
res = change_base_rev(res, 2, 10);
res.normalize();
return res;
}
void operator>>=(const bigint &x) {
(*this) = (*this) >> x;
}
void operator<<=(const bigint &x) {
(*this) = (*this) << x;
}
//builtin fuctions
int popcount() {
int res = 0;
bigint tmp = *this;
tmp = CB(tmp, 10, 2);
for (auto i : tmp.num)
res += i;
return res;
}
int ctz() {
bigint tmp = *this;
tmp = CB(tmp, 10, 2);
for (int i = 0; i < tmp.num.size(); i++)
if (tmp.num[i])
return i;
return 1;
}
//cin and cout
friend istream& operator>>(istream &stream, bigint &x) {
string s;
stream >> s;
x.toBig(s);
x.normalize();
return stream;
}
friend ostream& operator<<(ostream &stream, bigint &x) {
if (x.num.empty()) {
stream << 0;
return stream;
}
if (!x.num.empty() and x.sign == -1)
stream << '-';
stream << (x.num.empty() ? 0 : x.num.back());
for (int i = (int) x.num.size() - 2; i >= 0; i--)
stream << x.num[i];
return stream;
}
};
struct International_Olympiad_in_Informatics
{
int i,j,res[mxn];
bigint p[mxn],c[mxn][mxn];
bigint K(int k,int n) { return c[k][n+k-1]; }
void Work(int n,int a[])
{
p[0]=bigint(1);
for(i=1;i<=n;i++) p[i]=p[i-1]*bigint(256);
for(i=0;i<=261;i++)
for(j=i;j<=525;j++)
if(i==0) c[i][j]=bigint(1); else c[i][j]=c[i][j-1]+c[i-1][j-1];
bigint order=bigint(1);
for(i=1;i<=n;i++) order+=bigint(a[i])*p[n-i];
res[0]=-1;
for(i=1;i<=261;i++)
{
for(j=res[i-1];j<=255;j++)
{
bigint tg=K(261-i,255-j+1);
if(order>tg) order-=tg; else break;
}
res[i]=j;
}
}
} IOI;
void encode(int n,int m[])
{
for(int i=n;i>=1;i--) m[i]=m[i-1];
IOI.Work(n,m);
for(int i=1;i<=261;i++)
if(IOI.res[i]>-1) send(IOI.res[i]);
}
/*
int n,m[mxn],i;
int main()
{
freopen("encoder.inp","r",stdin);
freopen("encoder.out","w",stdout);
cin>>n;
for(i=0;i<n;i++) cin>>m[i];
encode(n,m);
}*/
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define mxn 555
//#define output(x) cout<<x<<" ";
#include "decoder.h"
#include "decoderlib.h"
using namespace std;
const int Dig = 10;
struct bigint {
deque<int> num;
int sign = 1;
//constructor
bigint() {
}
bigint(long long x) {
num.clear();
if (x < 0)
sign = -1, x = -x;
if (x == 0)
num.push_back(x);
while (x > 0) {
num.push_back(x % Dig);
x /= Dig;
}
}
bigint(int x) {
num.clear();
if (x < 0)
sign = -1, x = -x;
if (x == 0)
num.push_back(x);
while (x > 0) {
num.push_back(x % Dig);
x /= Dig;
}
}
bigint(const bigint &x) {
sign = x.sign;
num = x.num;
}
// change to int
friend int BtoI(const bigint &x) {
int res = 0, t = 1;
for (int i = 0; i < x.num.size(); i++)
res += t * x.num[i];
return res;
}
//absolut
friend bigint abs(const bigint &x) {
bigint res = x;
res.sign = 1;
return res;
}
//clear 0
void clr() {
while (!num.empty() and !num.back())
num.pop_back();
}
//normalize
void normalize() {
(*this).clr();
int carry = 0;
for (int i = 0; i < num.size(); i++) {
int t = num[i] + carry;
if (t < 0) {
t += Dig;
carry = -1;
num[i] = t;
}
else {
num[i] = t % Dig;
carry = t / Dig;
}
}
if (carry > 0)
num.push_back(carry);
if (carry < 0) {
sign *= -1;
num.push_back(-carry);
}
(*this).clr();
if (num.empty())
sign = 1;
}
//is 0
bool isZero() {
(*this).normalize();
return num.empty();
}
//compare operators
bool operator<(const bigint &x) const {
bigint a = (*this);
bigint b = x;
a.normalize();
b.normalize();
if (a.sign != b.sign)
return a.sign < b.sign;
bool res = false, flag = false;
if (a.num.size() != b.num.size()) {
res = (a.num.size() < b.num.size());
flag = true;
}
else {
for (int i = a.num.size() - 1; i >= 0; i--)
if (a.num[i] != b.num[i]) {
flag = true;
res = (a.num[i] < b.num[i]);
break;
}
}
if (!flag)
return false;
if (sign == -1)
return !res;
return res;
}
bool operator==(const bigint &x) const {
bigint a = (*this);
bigint b = x;
a.normalize();
b.normalize();
if (a.sign == b.sign and a.num.size() == b.num.size()) {
bool res = true;
for (int i = 0; i < a.num.size() and res; i++)
if (a.num[i] != b.num[i])
res = false;
return res;
}
else
return false;
}
bool operator<=(const bigint &x) const {
return (((*this) < x) or ((*this) == x));
}
bool operator>(const bigint &x) const {
return (!((*this) <= x));
}
bool operator>=(const bigint &x) const {
return (!((*this) < x));
}
bool operator!=(const bigint &x) const {
return (!((*this) == x));
}
friend bigint max(bigint &x, bigint &y) {
return (x > y? x: y);
}
friend bigint min(bigint &x, bigint &y) {
return (x < y? x: y);
}
//math operators
bigint operator+(const bigint &x) const {
if (sign == x.sign) {
bigint res;
res.sign = sign;
for (int i = 0; i < max(x.num.size(), num.size()); i++) {
int t = (i >= num.size()? 0: num[i]) + (i >= x.num.size()? 0: x.num[i]);
res.num.push_back(t);
}
res.normalize();
return res;
}
if (sign == -1)
return x - abs(*this);
else
return (*this) - abs(x);
}
bigint operator-(const bigint &x) const {
if (sign == x.sign) {
bigint res, a = abs(*this), b = abs(x);
a.clr();
b.clr();
if (a == b) {
res = 0;
return res;
}
if (b < a) {
for (int i = 0; i < a.num.size(); i++) {
int t = a.num[i] - (i >= b.num.size()? 0: b.num[i]);
res.num.push_back(t);
}
res.normalize();
}
else {
for (int i = 0; i < b.num.size(); i++) {
int t = b.num[i] - (i >= a.num.size()? 0: a.num[i]);
res.num.push_back(t);
}
res.normalize();
res.sign *= -1;
}
if (sign == -1)
res.sign *= -1;
return res;
}
if (sign == -1) {
bigint res = abs(*this) + x;
res.sign *= -1;
return res;
}
else
return (*this) + abs(x);
}
void operator+=(const bigint &x) {
(*this) = (*this) + x;
}
void operator-=(const bigint &x) {
(*this) = (*this) - x;
}
void operator++() {
(*this) += 1;
}
bigint operator++(int) {
bigint res;
++(*this);
return res;
}
void operator--() {
(*this) -= 1;
}
bigint operator--(int) {
bigint res;
--(*this);
return res;
}
bigint operator*(const bigint &x) const {
bigint res;
bigint a = (*this), b = x;
if (a.isZero() or b.isZero())
return 0;
a.clr();
b.clr();
for (int i = 0; i < b.num.size(); i++) {
bigint t;
for (int j = 1; j <= i; j++)
t.num.push_back(0);
for (int j = 0; j < a.num.size(); j++)
t.num.push_back(a.num[j] * b.num[i]);
t.normalize();
res += t;
}
res.normalize();
res.sign = a.sign * b.sign;
return res;
}
void operator*=(const bigint &x) {
(*this) = (*this) * x;
}
friend pair<bigint, bigint> dmod(const bigint &x, const bigint &y) {
bigint res, a = abs(x), b = abs(y), carry;
res.sign = y.sign * x.sign;
a.clr();
b.clr();
if (b.isZero())
return {-1, -1};
if (a < b) {
return {0, x};
}
int cnt = a.num.size() - 1;
for (int i = a.num.size() - 1; carry < b; i--) {
carry.num.push_front(a.num[i]);
cnt = i - 1;
}
for (int i = 1; i <= 10; i++) {
bigint t = b * i;
if (t > carry) {
res.num.push_front(i - 1);
t -= b;
carry -= t;
break;
}
}
for (int i = cnt; i >= 0; i--) {
carry.num.push_front(a.num[i]);
carry.normalize();
if (carry >= b) {
for (int j = 1; j <= 10; j++) {
bigint t = b * j;
if (t > carry) {
res.num.push_front(j - 1);
t -= b;
carry -= t;
break;
}
}
}
else {
res.num.push_front(0);
}
}
res.normalize();
if (res.sign == -1)
carry = y - x;
return {res, carry};
}
bigint operator/(const bigint &x) const {
pair<bigint, bigint> res = dmod((*this), x);
return res.first;
}
void operator/=(const bigint &x) {
(*this) = (*this) / x;
}
bigint operator%(const bigint &x) const {
pair<bigint, bigint> res = dmod((*this), x);
return res.second;
}
void operator%=(const bigint &x) {
(*this) = (*this) % x;
}
friend bigint pow(const bigint &x, const bigint &y) {
bigint tmp = y;
if (tmp.isZero())
return 1;
bigint res = 1, t = y, a = x;
pair<bigint, bigint> dm;
while (t > 0) {
if ((t % 2) == 1)
res = res * a;
a *= a;
t /= 2;
}
return res;
}
friend bigint gcd(bigint x, bigint y) {
return (y.isZero()? x: gcd(y, x % y));
}
friend bigint lcm(const bigint &x, const bigint &y) {
return (x * y) / gcd(x, y);
}
friend bigint sqrt(const bigint &x) {
if (x.sign == -1)
return -1;
bigint carry, res, lef;
deque<pair<int, int>> t;
for (int i = 0; i < x.num.size(); i += 2) {
if (i + 1 == x.num.size())
t.push_front({x.num[i], 1});
else
t.push_front({x.num[i] + x.num[i + 1] * 10, 2});
}
for (int i = 0; i < t.size(); i++) {
if (t[i].second == 1)
carry.num.push_front(t[i].first);
else
carry.num.push_front(t[i].first / 10), carry.num.push_front(t[i].first % 10);
carry.normalize();
lef.num.push_front(0);
for (int i = 1; i <= 10; i++) {
lef.num[0] = i;
bigint tmp = (lef) * i;
if (tmp > carry) {
lef.num[0] = i - 1;
tmp = lef * (i - 1);
carry -= tmp;
lef += (i - 1);
res.num.push_front(i - 1);
break;
}
}
}
res.normalize();
return res;
}
//string to bigint and bigint to string
void toBig(string &s) {
if (s[0] == '-') {
sign = -1;
s = s.substr(1);
}
else
sign = 1;
reverse(s.begin(), s.end());
num.clear();
for (int i = (s[0] == '-'); i < s.size(); i += Dig / 10) {
string sp;
for (int j = i; j < i + (Dig / 10); j++)
sp += s[j];
long long t = stol(sp);
num.push_back(t);
}
}
friend string to_string(const bigint &x) {
string res;
if (x.num.empty()) {
res += '0';
return res;
}
if (x.sign == -1)
res += '-';
for (int i = x.num.size() - 1; i >= 0; i--) {
string t = to_string(x.num[i]);
reverse(t.begin(), t.end());
res += t;
}
return res;
}
//change base
friend bigint change_base(const bigint &a, const int y, const int x) {
if (y == x)
return a;
bigint res, t = change_base_rev(a, y, 10);
t.normalize();
while (t > 0) {
res.num.push_back(BtoI(t % x));
t /= x;
}
return res;
}
friend bigint change_base_rev(const bigint &a, const int y, const int x) {
if (y == x)
return a;
if (x == 10) {
bigint res, t = 1, b = a;
b.clr();
for (int i = 0; i < b.num.size(); i++)
res += t * b.num[i], t *= y;
return res;
}
bigint t = change_base_rev(a, y, 10);
return change_base(t, 10, x);
}
friend bigint CB(const bigint &a, int y, int x) {
if (x > y)
return change_base_rev(a, y, x);
return change_base(a, y, x);
}
//bitwise operator
bigint operator^(const bigint &x) const {
bigint res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
int d1 = 0, d2 = 0;
if (i < a.num.size())
d1 = a.num[i];
if (i < b.num.size())
d2 = b.num[i];
res.num.push_back(d1 ^ d2);
}
res.clr();
res = change_base_rev(res, 2, 10);
res.normalize();
return res;
}
bigint operator&(const bigint &x) const {
bigint res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
int d1 = 0, d2 = 0;
if (i < a.num.size())
d1 = a.num[i];
if (i < b.num.size())
d2 = b.num[i];
res.num.push_back(d1 & d2);
}
res.clr();
res = change_base_rev(res, 2, 10);
res.normalize();
return res;
}
bigint operator|(const bigint &x) const {
bigint res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
int d1 = 0, d2 = 0;
if (i < a.num.size())
d1 = a.num[i];
if (i < b.num.size())
d2 = b.num[i];
res.num.push_back(d1 | d2);
}
res.clr();
res = change_base_rev(res, 2, 10);
res.normalize();
return res;
}
void operator^=(const bigint &x) {
(*this) = (*this) ^ x;
}
void operator&=(const bigint &x) {
(*this) = (*this) & x;
}
void operator|=(const bigint &x) {
(*this) = (*this) | x;
}
bigint operator<<(const bigint &x) {
bigint res = change_base((*this), 10, 2);
for (bigint i = 0; i < x; i++)
res.num.push_front(0);
res = change_base_rev(res, 2, 10);
res.normalize();
return res;
}
bigint operator>>(const bigint &x) {
bigint res = change_base((*this), 10, 2);
bigint t = (int)res.num.size();
for (bigint i = 0; i < min(x, t); i++)
res.num.pop_front();
res = change_base_rev(res, 2, 10);
res.normalize();
return res;
}
void operator>>=(const bigint &x) {
(*this) = (*this) >> x;
}
void operator<<=(const bigint &x) {
(*this) = (*this) << x;
}
//builtin fuctions
int popcount() {
int res = 0;
bigint tmp = *this;
tmp = CB(tmp, 10, 2);
for (auto i : tmp.num)
res += i;
return res;
}
int ctz() {
bigint tmp = *this;
tmp = CB(tmp, 10, 2);
for (int i = 0; i < tmp.num.size(); i++)
if (tmp.num[i])
return i;
return 1;
}
//cin and cout
friend istream& operator>>(istream &stream, bigint &x) {
string s;
stream >> s;
x.toBig(s);
x.normalize();
return stream;
}
friend ostream& operator<<(ostream &stream, bigint &x) {
if (x.num.empty()) {
stream << 0;
return stream;
}
if (!x.num.empty() and x.sign == -1)
stream << '-';
stream << (x.num.empty() ? 0 : x.num.back());
for (int i = (int) x.num.size() - 2; i >= 0; i--)
stream << x.num[i];
return stream;
}
};
struct International_Olympiad_in_Informatics
{
int i,j,res[mxn];
bigint p[mxn],c[mxn][mxn];
bigint K(int k,int n) { return c[k][n+k-1]; }
void Work(int n,int m,int a[])
{
p[0]=bigint(1);
for(i=1;i<=n;i++) p[i]=p[i-1]*bigint(256);
for(i=0;i<=261;i++)
for(j=i;j<=525;j++)
if(i==0) c[i][j]=bigint(1); else c[i][j]=c[i][j-1]+c[i-1][j-1];
sort(a+1,a+m+1);
bigint order=bigint(1);
a[0]=-1;
for(i=1;i<=m;i++)
{
for(j=a[i-1];j<a[i];j++)
order+=K(m-i,255-j+1);
}
for(i=1;i<=n;i++)
{
for(j=0;j<=255;j++)
if(order>p[n-i]) order-=p[n-i]; else break;
res[i]=j;
}
}
} IOI;
void decode(int n,int l,int x[])
{
for(int i=l;i>=1;i--) x[i]=x[i-1];
IOI.Work(n,l,x);
for(int i=1;i<=n;i++) output(IOI.res[i]);
}
/*
int n,l,x[mxn],i;
int main()
{
freopen("decoder.inp","r",stdin);
freopen("decoder.out","w",stdout);
cin>>n>>l;
for(i=0;i<l;i++) cin>>x[i];
decode(n,l,x);
}
*/
Compilation message
encoder.cpp: In function 'int BtoI(const bigint&)':
encoder.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < x.num.size(); i++)
| ~~^~~~~~~~~~~~~~
encoder.cpp: In member function 'void bigint::normalize()':
encoder.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < num.size(); i++) {
| ~~^~~~~~~~~~~~
encoder.cpp: In member function 'bool bigint::operator==(const bigint&) const':
encoder.cpp:146:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int i = 0; i < a.num.size() and res; i++)
| ~~^~~~~~~~~~~~~~
encoder.cpp: In member function 'bigint bigint::operator+(const bigint&) const':
encoder.cpp:178:22: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
178 | for (int i = 0; i < max(x.num.size(), num.size()); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
encoder.cpp:179:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | int t = (i >= num.size()? 0: num[i]) + (i >= x.num.size()? 0: x.num[i]);
| ~~^~~~~~~~~~~~~
encoder.cpp:179:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | int t = (i >= num.size()? 0: num[i]) + (i >= x.num.size()? 0: x.num[i]);
| ~~^~~~~~~~~~~~~~~
encoder.cpp: In member function 'bigint bigint::operator-(const bigint&) const':
encoder.cpp:200:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
200 | for (int i = 0; i < a.num.size(); i++) {
| ~~^~~~~~~~~~~~~~
encoder.cpp:201:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | int t = a.num[i] - (i >= b.num.size()? 0: b.num[i]);
| ~~^~~~~~~~~~~~~~~
encoder.cpp:207:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for (int i = 0; i < b.num.size(); i++) {
| ~~^~~~~~~~~~~~~~
encoder.cpp:208:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
208 | int t = b.num[i] - (i >= a.num.size()? 0: a.num[i]);
| ~~^~~~~~~~~~~~~~~
encoder.cpp: In member function 'bigint bigint::operator*(const bigint&) const':
encoder.cpp:255:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
255 | for (int i = 0; i < b.num.size(); i++) {
| ~~^~~~~~~~~~~~~~
encoder.cpp:259:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
259 | for (int j = 0; j < a.num.size(); j++)
| ~~^~~~~~~~~~~~~~
encoder.cpp: In function 'bigint sqrt(const bigint&)':
encoder.cpp:358:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
358 | for (int i = 0; i < x.num.size(); i += 2) {
| ~~^~~~~~~~~~~~~~
encoder.cpp:359:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
359 | if (i + 1 == x.num.size())
| ~~~~~~^~~~~~~~~~~~~~~
encoder.cpp:364:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
364 | for (int i = 0; i < t.size(); i++) {
| ~~^~~~~~~~~~
encoder.cpp: In member function 'void bigint::toBig(std::string&)':
encoder.cpp:398:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
398 | for (int i = (s[0] == '-'); i < s.size(); i += Dig / 10) {
| ~~^~~~~~~~~~
encoder.cpp: In function 'bigint change_base_rev(const bigint&, int, int)':
encoder.cpp:439:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
439 | for (int i = 0; i < b.num.size(); i++)
| ~~^~~~~~~~~~~~~~
encoder.cpp: In member function 'bigint bigint::operator^(const bigint&) const':
encoder.cpp:456:21: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
456 | for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
encoder.cpp:458:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
458 | if (i < a.num.size())
| ~~^~~~~~~~~~~~~~
encoder.cpp:460:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
460 | if (i < b.num.size())
| ~~^~~~~~~~~~~~~~
encoder.cpp: In member function 'bigint bigint::operator&(const bigint&) const':
encoder.cpp:471:21: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
471 | for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
encoder.cpp:473:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
473 | if (i < a.num.size())
| ~~^~~~~~~~~~~~~~
encoder.cpp:475:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
475 | if (i < b.num.size())
| ~~^~~~~~~~~~~~~~
encoder.cpp: In member function 'bigint bigint::operator|(const bigint&) const':
encoder.cpp:486:21: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
486 | for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
encoder.cpp:488:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
488 | if (i < a.num.size())
| ~~^~~~~~~~~~~~~~
encoder.cpp:490:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
490 | if (i < b.num.size())
| ~~^~~~~~~~~~~~~~
encoder.cpp: In member function 'int bigint::ctz()':
encoder.cpp:545:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
545 | for (int i = 0; i < tmp.num.size(); i++)
| ~~^~~~~~~~~~~~~~~~
decoder.cpp: In function 'int BtoI(const bigint&)':
decoder.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < x.num.size(); i++)
| ~~^~~~~~~~~~~~~~
decoder.cpp: In member function 'void bigint::normalize()':
decoder.cpp:82:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < num.size(); i++) {
| ~~^~~~~~~~~~~~
decoder.cpp: In member function 'bool bigint::operator==(const bigint&) const':
decoder.cpp:146:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for (int i = 0; i < a.num.size() and res; i++)
| ~~^~~~~~~~~~~~~~
decoder.cpp: In member function 'bigint bigint::operator+(const bigint&) const':
decoder.cpp:178:22: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
178 | for (int i = 0; i < max(x.num.size(), num.size()); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
decoder.cpp:179:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | int t = (i >= num.size()? 0: num[i]) + (i >= x.num.size()? 0: x.num[i]);
| ~~^~~~~~~~~~~~~
decoder.cpp:179:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
179 | int t = (i >= num.size()? 0: num[i]) + (i >= x.num.size()? 0: x.num[i]);
| ~~^~~~~~~~~~~~~~~
decoder.cpp: In member function 'bigint bigint::operator-(const bigint&) const':
decoder.cpp:200:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
200 | for (int i = 0; i < a.num.size(); i++) {
| ~~^~~~~~~~~~~~~~
decoder.cpp:201:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | int t = a.num[i] - (i >= b.num.size()? 0: b.num[i]);
| ~~^~~~~~~~~~~~~~~
decoder.cpp:207:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
207 | for (int i = 0; i < b.num.size(); i++) {
| ~~^~~~~~~~~~~~~~
decoder.cpp:208:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
208 | int t = b.num[i] - (i >= a.num.size()? 0: a.num[i]);
| ~~^~~~~~~~~~~~~~~
decoder.cpp: In member function 'bigint bigint::operator*(const bigint&) const':
decoder.cpp:255:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
255 | for (int i = 0; i < b.num.size(); i++) {
| ~~^~~~~~~~~~~~~~
decoder.cpp:259:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
259 | for (int j = 0; j < a.num.size(); j++)
| ~~^~~~~~~~~~~~~~
decoder.cpp: In function 'bigint sqrt(const bigint&)':
decoder.cpp:358:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
358 | for (int i = 0; i < x.num.size(); i += 2) {
| ~~^~~~~~~~~~~~~~
decoder.cpp:359:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
359 | if (i + 1 == x.num.size())
| ~~~~~~^~~~~~~~~~~~~~~
decoder.cpp:364:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
364 | for (int i = 0; i < t.size(); i++) {
| ~~^~~~~~~~~~
decoder.cpp: In member function 'void bigint::toBig(std::string&)':
decoder.cpp:398:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
398 | for (int i = (s[0] == '-'); i < s.size(); i += Dig / 10) {
| ~~^~~~~~~~~~
decoder.cpp: In function 'bigint change_base_rev(const bigint&, int, int)':
decoder.cpp:439:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
439 | for (int i = 0; i < b.num.size(); i++)
| ~~^~~~~~~~~~~~~~
decoder.cpp: In member function 'bigint bigint::operator^(const bigint&) const':
decoder.cpp:456:21: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
456 | for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
decoder.cpp:458:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
458 | if (i < a.num.size())
| ~~^~~~~~~~~~~~~~
decoder.cpp:460:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
460 | if (i < b.num.size())
| ~~^~~~~~~~~~~~~~
decoder.cpp: In member function 'bigint bigint::operator&(const bigint&) const':
decoder.cpp:471:21: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
471 | for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
decoder.cpp:473:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
473 | if (i < a.num.size())
| ~~^~~~~~~~~~~~~~
decoder.cpp:475:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
475 | if (i < b.num.size())
| ~~^~~~~~~~~~~~~~
decoder.cpp: In member function 'bigint bigint::operator|(const bigint&) const':
decoder.cpp:486:21: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
486 | for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
decoder.cpp:488:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
488 | if (i < a.num.size())
| ~~^~~~~~~~~~~~~~
decoder.cpp:490:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
490 | if (i < b.num.size())
| ~~^~~~~~~~~~~~~~
decoder.cpp: In member function 'int bigint::ctz()':
decoder.cpp:545:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
545 | for (int i = 0; i < tmp.num.size(); i++)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
172 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
164 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
166 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
168 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
196 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
168 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
168 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Execution timed out |
2351 ms |
262144 KB |
Time limit exceeded |
| 5 |
Runtime error |
165 ms |
262144 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
175 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
169 ms |
262144 KB |
Execution killed with signal 9 |
