gcj B but bad impl

ll sum(const vector<ll>& a){
    ll ans = 0;
    for(ll x : a) ans += x;
    return ans;
}
void solve(){
    int n;
    cin >> n;
    assert( n == 100);
    //ternary?
    vector<ll> oup;
    ll p3 = 1;
    for( p3 = 1; p3<=1e9; p3*=3ll){
        oup.pb(p3);
        oup.pb(p3*2);
    }
    oup.pb(p3/2);
    oup.pb(p3/2 +1);
    int aux = 100 - sz(oup);
    //cout << aux << "\n";
    for(int i = 0; i<aux; i++){
        oup.pb(1e9 -i);
    }
    sort(all(oup));
    oup.resize(unique(all(oup)) - oup.begin());
    assert(sz(oup) == 100);
    //for(ll x : oup) cout << x << " " ;
    //cout << endl;

    for(ll x : oup){
        assert(1 <= x && x <= 1e9);
        cout << x << " " ;
    }
    cout << endl;
    vector<ll> inp(n);
    int cnt = 1e9 -100;
    for(ll& x : inp){
        //cnt++;
        cin >> x;
        //x = cnt;
    }
    sort(all(inp));
    vector<ll> ans1, ans2;
    ll tot1 = 0, tot2 = 0;
    for(int i = 0; i<n; i+=2){
        tot1 += inp[i];
        tot2 += inp[i+1];
        ans1.pb(inp[i]);
        ans2.pb(inp[i+1]);
    }
    assert(tot2 >= tot1);
    ll diff = tot2 - tot1;
    for(ll p = 1; p<=1e9; p *= 3ll){
        ll dig = diff/p %3ll;
        if(dig == 0){
            ans2.pb(p);
            ans2.pb(p*2ll);
            diff += p*3ll;
        }else if(dig == 2){
            ans1.pb(p);
            ans2.pb(p*2ll);
            diff += p;
        }else{
            ans2.pb(p);
            ans1.pb(p*2);
            //diff += p*2ll;
        }
    }
    if(diff/p3 %3ll == 1){
        ans1.pb(p3/2);
        ans1.pb(p3/2 +1);
        //ans1.pb(1);
    }else{
        assert(0);
    }
    for(int i = 0; i<aux/4; i++){
        ans1.pb(1e9 - i);
        ans1.pb(1e9 - aux + (i+1));
        ans2.pb(1e9 - aux/2 - i);
        ans2.pb(1e9 - aux/2 +(i+1));
    }
    vector<ll> fa = ans1;
    for(ll x : ans2) fa.pb(x);
    sort(all(fa));
    vector<ll> sa = inp;
    for(ll x : oup) sa.pb(x);
    sort(all(sa));
    assert(fa == sa);
    //for(int i = 0; i<sz(fa); i++){
        //cerr << fa[i] << " " << sa[i] << endl;
    //}
    assert(sum(ans1) == sum(ans2));
    //cerr << sum(ans1) << " " << (ll)sum(ans2) << "\n";
    //cerr << (ll)(sum(ans1) - sum(ans2)) << "\n";
    //cerr << p3 << "\n";



    for(ll x : ans1){
        assert(binary_search(all(oup), x) || binary_search(all(inp), x));
        cout << x << " ";
    }
    cout << endl;
}