#include <bits/stdc++.h>
#include "books.h"
using namespace std;
#define ll long long
const ll N = 1e5+5;
ll dp[N];
void solve(int N, int K, long long A, int S) {
memset(dp, -1, sizeof(dp));
ll l = 1;
ll r = N;
while (l < r) {
ll mid = (l+r)>>1;
if (dp[mid] == -1) dp[mid] = skim(mid);
if (dp[mid] < A) l = mid+1;
else r = mid;
}
if (dp[l] == -1) dp[l] = skim(l);
vector<int> test;
test.push_back(l);
ll cnt = dp[l];
for (ll i = 1; i <= K-1; i++) {
if (dp[i] == -1) dp[i] = skim(i);
cnt += dp[i];
cerr << cnt << endl;
test.push_back(i);
}
if (K-1 < l && A <= cnt && cnt <= A*2) {
answer(test);
return;
}
if (K >= l) {
impossible();
return;
}
cnt = 0;
vector<int> ans;
for (ll i = 1; i <= K; i++) {
if (dp[i] == -1) dp[i] = skim(i);
cnt += dp[i];
ans.push_back(i);
}
if (cnt > 2*A) {
impossible();
return;
}
for (ll i = l-1; i >= l-K; i--) {
if (dp[i] == -1) dp[i] = skim(i);
}
ll curr = K-1;
r = l-1;
while (curr >= 0 && cnt < A) {
cnt -= dp[K - curr];
cnt += dp[r];
ans[K-curr-1] = r;
curr--;
r--;
}
if (cnt < A) answer(ans);
impossible();
}
