#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n, k, s;
ll a;
void solve(int N, int K, ll A, int S) {
n = N;
k = K;
a = A;
s = S;
// binary search for first position of A
// either use that and all k-1 smallest indices, or only use elements less than a
// when using elements less than a, if their sum is less than a, just move the latst index to the back (will be less than a)
int idx = -1;
int lo = 1, hi = n;
while (lo <= hi) {
int mid = (lo + hi) / 2;
ll val = skim(mid);
if (val >= a) {
hi = mid-1;
}
else {
lo = mid+1;
idx = mid;
}
}
if (idx == -1) { // k >= 3
impossible();
return;
}
if (k - idx >= 2) {
impossible();
return;
}
// try k-1 first vals and a value >= a
vector<ll> vals(k+1);
ll tot = 0;
for (int i = 1; i <= k; i++) {
vals[i] = skim(i);
tot += vals[i];
}
if (tot > 2 * a) {
impossible();
return;
}
if (idx + 1 <= n) {
ll nextVal = skim(idx+1);
tot -= vals[k];
tot += nextVal;
if (tot >= a && tot <= 2 * a) {
vector<int> fin;
for (int i = 1; i <= k-1; i++) fin.push_back(i);
fin.push_back(idx+1);
answer(fin);
return;
}
tot -= nextVal;
tot += vals[k];
}
int bound = idx;
vector<int> index(k+1);
for (int i = 1; i <= k; i++) index[i] = i;
for (int i = k; i >= 1; i--) {
if (tot >= a && tot <= 2*a) {
vector<int> fin;
for (int i = 1; i <= k; i++) fin.push_back(i);
answer(fin);
return;
}
if (i == bound) {
impossible();
return;
}
ll nxtVal = skim(bound);
tot += nxtVal;
tot -= vals[i];
index[i] = bound;
bound--;
}
if (tot >= a && tot <= 2*a) {
vector<int> fin;
for (int i = 1; i <= k; i++) fin.push_back(i);
answer(fin);
return;
}
impossible();
/*
vector<ll> arr(n+1);
for (int i = 1; i <= k; i++) {
arr[i] = skim(i);
}
ll currS = 0;
vector<int> index(k+2);
for (int i = 1; i <= k; i++) {
currS += arr[i];
index[i] = i;
}
index[k+1] = n+1;
for (int curr = k; curr >= 1; curr--) {
if (currS >= a && currS <= 2*a) break;
int allow = index[curr+1] - 1;
if (allow == curr) continue;
int lo = curr+1, hi = allow;
int idx = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
ll val = skim(mid);
ll tot = currS - arr[curr] + val;
if (tot >= a && tot <= 2 * a) {
index[curr] = mid;
vector<int> fin;
for (int i = 1; i <= k; i++) {
fin.push_back(index[i]);
}
answer(fin);
return;
}
if (tot > 2 * a) {
hi = mid-1;
}
else {
idx = mid;
lo = mid+1;
}
}
if (idx == -1) {
impossible();
return;
}
currS -= arr[curr];
currS += arr[idx];
index[curr] = idx;
}
if (currS > 2 * a || currS < a) {
impossible();
return;
}
else {
vector<int> fin;
for (int i = 1; i <= k; i++) {
fin.push_back(index[i]);
}
answer(fin);
return;
}*/
}
