#include <bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
// books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
// g++ books.cpp grader.cpp
// in this folder.
//
void solve(int N, int K, long long A, int S) {
// TODO implement this function
vector<ll> first;
map<ll,ll> checked;
ll total=0;
for (int i=1;i<=K;i++){
ll temp = skim(i);
total += temp;
first.push_back(temp);
checked[i] = temp;
}
vector<int> ans;
for (int i=1;i<=K;i++){
ans.push_back(i);
}
if (total > A*2) impossible();
if (total >= A) answer(ans);
ll l=1,r=N+1;
while (l<r){
ll m = l+(r-l)/2;
ll temp = skim(m);
checked[m] = temp;
if (temp<A) l=m+1;
else r=m;
}
if (total-checked[K]+checked[l] <= 2*A) {
vector<int> ans2;
for (int i=1;i<K;i++){
ans2.push_back(i);
}
ans2.push_back(l);
answer(ans2);
}
answer({1});
ll l2;
if (checked[l-1]!=0) l2 = checked[l-1];
else l2 = skim(l-1);
checked[l-1] = l2;
vector<int> ans2;
ans2.push_back(l-1);
total -= checked[1];
if (total + l2 >= A) {
for (int i=2;i<=K;i++) ans2.push_back(i);
answer(ans2);
}
total += l2;
for (int i=0;i<K-1;i++){
l--;
if (checked[l-1]!=0) l2 = checked[l-1];
else l2 = skim(l-1);
checked[l-1] = l2;
ans2.push_back(l-1);
total -= checked[i+2];
if (total + l2 >= A){
for (int j=i+3;j<=K;j++) ans2.push_back(j);
answer(ans2);
}
total += l2;
}
impossible();
}
