#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
#define pr pair
typedef pr<ll,ll> prll;
#define umap unordered_map
#define fi first
#define se second
#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(a); (i)>=(a); (i)--)
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define sz size
#define mxN (100010ll)
#define INF (LLONG_MAX-100ll)
// skim(3);
// impossible();
// answer({1,3});
ll n, k, A, A2, big;
vcll ar(mxN,-1);
inline ll peak (ll i) { return ar[i]==-1 ? skim(i) : ar[i]; }
inline ll find_big()
{
ll l=1, r=n, big2=n+1;
while (l<=r)
{
ll mid=(l+r)/2;
if (peak(mid)>A)
{
big2=mid;
r=mid-1;
}
else
{
l=mid+1;
}
}
return big2;
}
inline vc<int> rng (vcll a, ll l, ll r)
{
vc<int> res;
ll i;
f0r(i,l,r) res.pb(a[i]);
return res;
}
inline vc<int> normrng (ll l, ll r)
{
vc<int> res;
ll i;
f0r(i,l,r) res.pb(i);
return res;
}
inline vc<int> merge (vc<int> a, vc<int> b)
{
vc<int> res;
for (ll x:a) res.pb(x);
for (ll x:b) res.pb(x);
return res;
}
inline vc<int> bf (vc<int> inds1)
{
vcll inds;
for (ll x:inds1) inds.pb(x);
ll k1=inds.sz();
if (k1<k) return {};
vcll nums;
nums.pb(-1);
for (ll i:inds) nums.pb(peak(i));
ll s=0, i;
f0r(i,1,k) s+=nums[i];
if (A<=s and s<=A2) return rng(inds,0,k-1);
f0r(i,i,k1)
{
s += nums[i] - nums[i-k];
if (A<=s and s<=A2) return rng(inds,i-k,i-1);
}
return {};
}
void solve(int N1, int K1, long long A1, int S1)
{
n=N1; k=K1; A=A1; A2=2*A;
if (n<=S1)
{
vc<int> ans=bf(normrng(1,n));
if (ans.sz()) answer(ans);
impossible();
}
big=find_big();
if (big==n+1)
{
ar[big]=INF;
}
if (big==1)
{
if (peak(big<=A2) and k==1) answer({1});
impossible();
}
if (big-1<=20)
{
vc<int> ans=bf(normrng(1,big-1));
if (ans.sz()) answer(ans);
A-=peak(big);
A2-=peak(big);
if (A2<=0) impossible();
ans=bf(normrng(1,big-1)); // TODO
if (ans.sz())
{
ans.pb(big);
answer(ans);
}
impossible();
}
// edge cases
vc<int> inds = merge(normrng(1,k), normrng(big-k,big-1));
vc<int> ans=bf(inds);
if (ans.sz()) answer(ans);
A-=peak(big);
A2-=peak(big);
if (A2<=0) impossible();
ans=bf(inds);
if (ans.sz())
{
ans.pb(big);
answer(ans);
}
impossible();
}
