#include "books.h"
#include <bits/stdc++.h>
#ifndef EVAL
#include "grader.cpp"
#endif
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
int mod = 1e9+7;
ll modulo(ll a) {
return ((a % mod) + mod) % mod;
}
ll add(ll a, ll b) {
return modulo(a + b);
}
ll mult(ll a, ll b) {
return modulo(a * b);
}
ll binpow(ll a, ll b) {
ll res = 1;
while (b) {
if (b&1) {
res = mult(res, a);
}
a = mult(a, a);
b >>= 1;
}
return res;
}
const int MX = 1e5+7;
ll val[MX];
ll ask(int i) {
if (val[i] > 0) return val[i];
return val[i] = skim(i);
}
void solve(int n, int k, long long a, int s) {
vector <ll> pref, suff;
ll sum = 0, l = 1, r = n+1;
while (l < r) {
int mid = (l+r) >> 1;
if (ask(mid) > a) {
r = mid;
}
else {
l = mid+1;
}
}
for (int i = 1; i < k; i++) {
sum += ask(i);
}
int ind = l;
if (ind < k || sum + ask(k) > 2*a) {
impossible();
return;
}
if (ind != n+1 && a <= ask(ind)+sum && ask(ind)+sum <= a*2) {
vector <int> ans(k);
iota(all(ans), 1);
ans.back() = ind;
answer(ans);
return;
}
pref.pb(0); suff.pb(0);
for (int i = 1; i <= k; i++) {
pref.pb(ask(i)+pref.back());
}
for (int i = ind-1; i >= ind-k; i--) {
suff.pb(ask(i)+suff.back());
}
for (int i = 0; i <= k; i++) {
sum = pref[k-i]+suff[i];
if (sum > 2*a) impossible();
if (a <= sum && sum <= 2*a) {
vector <int> ans;
for (int j = 1; j <= k-i; j++) {
ans.pb(j);
}
for (int j = 1; j <= i; j++) {
ans.pb(ind-j);
}
answer(ans);
return;
}
}
impossible();
}
/*
15 3 42 170
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
*/
