#include<bits/stdc++.h>
#include "books.h"
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pb push_back
#define sz(v) (ll)(v.size())
#define f first
#define s second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
const ll sz = 1e5+5;
ll a[sz];
ll ask(ll v)
{
if(a[v])
return a[v];
return a[v] = skim(v);
}
void solve(int N, int K, long long A, int S)
{
for(int i = 1; i <= N; i++)
a[i] = 0;
int l = 1, r = N, bst = N+1;
while(l <= r)
{
int mid = (l + r) / 2;
if(ask(mid) >= A)
{
bst = mid;
r = mid - 1;
}
else
l = mid + 1;
}
if(bst < K)
{
impossible();
return;
}
if(bst <= N)
{
ll sm = 0;
for(ll i = 1; i <= K - 1; i++)
sm += ask(i);
sm += ask(bst);
if(A <= sm && sm <= 2 * A)
{
vi v;
for(ll i = 1; i <= K - 1; i++)
v.pb(i);
v.pb(bst);
answer(v);
return;
}
}
set<ll>st;
for(ll i = 1; i <= K; i++)
st.insert(i);
for(ll i = bst - K; i <= bst-1; i++)
st.insert(i);
vl v;
for(auto u : st)
v.pb(u);
for(ll i = 0; i < (1 << sz(v)); i++)
{
ll sm = 0, cnt = 0;
for(ll j = 0; j < sz(v); j++)
{
if((i >> j) & 1)
sm += ask(v[j]), cnt++;
}
if(sm >= A && sm <= 2 * A && cnt == K)
{
vi res;
for(ll j = 0; j < sz(v); j++)
{
if((i >> j) & 1)
res.pb(v[j]);
}
answer(res);
return;
}
}
impossible();
}
