#include <bits/stdc++.h>
#include "books.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;
const ll NMAX = 1000001;
const ll VMAX = 1001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 31;
const ll nr_of_bits = 21;
map <int, ll> mp;
ll afla(int i) {
if(mp.find(i) != mp.end())
return mp[i];
return mp[i] = skim(i);
}
void solve(int N, int K, long long A, int S) {
ll sum = 0;
vector <int> first;
for(int i = 1; i <= K; i++) {
ll acum = afla(i);
first.push_back(i);
sum += acum;
}
if(sum > 2 * A) {
impossible();
return;
}
if(sum >= A && sum <= 2 * A) {
answer(first);
return;
}
reverse(first.begin(), first.end()); /// eliminam pe cel mai mic
int r = 0, pas = (1 << nr_of_bits);
while(pas) {
if(r + pas <= N) {
ll acum = afla(r + pas);
if(acum <= A) {
r += pas;
}
}
pas /= 2;
}
vector <int> second;
sum -= afla(first.back());
first.pop_back();
if(r < N && afla(r + 1) + sum >= A && afla(r + 1) + sum <= 2 * A) {
first.push_back(r + 1);
for(auto x : second)
first.push_back(x);
answer(first);
return;
}
sum += afla(r);
second.push_back(r);
int ini = r;
r--;
while(first.size()) {
if(sum >= A && sum <= 2 * A) {
for(auto x : second)
first.push_back(x);
answer(first);
return;
}
sum -= afla(first.back());
first.pop_back();
sum += afla(r);
second.push_back(r);
r--;
if(ini < N && afla(ini + 1) + sum - afla(ini) >= A && afla(ini + 1) + sum - afla(ini) <= 2 * A) {
first.push_back(ini + 1);
for(auto x : second){
if(x != ini)
first.push_back(x);
}
answer(first);
return;
}
}
if(sum >= A && sum <= 2 * A) {
for(auto x : second)
first.push_back(x);
answer(first);
return;
}
impossible();
}
