#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using i64 = long long;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)
#define ALL(x) (x).begin(), (x).end()
i64 skim2(int v) { return skim(v + 1); }
void solve(int N, int K, long long A, int S) {
vector<i64> data(N, -1);
REP(i, K) data[i] = skim2(i);
if (accumulate(data.begin(), data.begin() + K, 0ll) > 2 * A) {
impossible();
return;
}
vector<int> ked(K);
REP(i, K) ked[i] = N - (K - i);
auto eval = [&](int i, int m) {
i64 res = 0;
REP(x, i) res += data[x];
REP3(x, i + 1, K) res += data[ked[x]];
return res + data[m];
};
auto rtrn = [&](int i, int m) {
vector<int> ans;
REP(x, i) ans.push_back(x);
REP3(x, i + 1, K) ans.push_back(ked[x]);
ans.push_back(m);
sort(ALL(ans));
for (auto &e : ans) ++e;
answer(ans);
return;
};
if (A <= eval(K - 1, K - 1) and eval(K - 1, K - 1) <= 2 * A) {
rtrn(K - 1, K - 1);
return;
}
RVP(i, K) {
const int j = min(i == K - 1 ? N - 1 : (ked[i + 1] - 1), ked[i]);
if (data[j] == -1) data[j] = skim2(j);
const auto res = eval(i, j);
if (A <= res and res <= 2 * A) {
rtrn(i, j);
return;
} else {
if (res < A) {
ked[i] = j;
continue;
}
int ok = i, ng = j;
while (ng - ok > 1) {
const int mid = (ok + ng) / 2;
if (data[mid] == -1) data[mid] = skim2(mid);
const auto r = eval(i, mid);
if (r <= A)
ok = mid;
else
ng = mid;
}
if (A <= eval(i, ng) and eval(i, ng) <= 2 * A) {
rtrn(i, ng);
return;
}
ked[i] = ok;
}
}
impossible();
}
