#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;
//
// --- 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_sample.cpp sample_grader.cpp
// in this folder.
//
ll val[100005];
void solve(int N, int K, long long A, int S) {
// TODO implement this function
ll csum = 0;
for(int i=1;i<=K;i++) {
val[i] = skim(i);
csum += val[i];
}
if(csum > 2*A) {impossible(); return;}
if(csum >= A) {
vector<int> vecss(K);
for(int i=0;i<K;i++) vecss[i] = i+1;
answer(vecss);
return;
}
csum -= val[K];
int l = K, r = N;
while(l <= r) {
int mid = (l+r) >> 1;
val[mid] = skim(mid);
if(csum + val[mid] < A) l = mid+1;
else r=mid-1;
}
l = r;
//wttttttf
//123,...,K-1, l is surely less than A
if(l != N) {
val[l+1] = skim(l+1);
if(csum + val[l+1] >= A && csum + val[l+1] <= 2*A) {
vector<int> vecss(K);
for(int i=0;i<K-1;i++) vecss[i] = i+1;
vecss[K-1] = l+1;
answer(vecss);
return;
}
}
//lolllllllllllllllllllllllllllllllllllllllll
for(int i=2;i<=K;i++) {
csum = 0;
vector<int> frfr;
for(int j=1;j<=K-i;j++) {
csum += val[j];
frfr.push_back(j);
}
val[l-i+1] = skim(l-i+1);
for(int j=l-i+1;j<=l;j++) {
csum += val[j];
frfr.push_back(j);
}
if(csum >= A && csum <= 2*A) {
answer(frfr);
return;
}
}
impossible();
/*
if (skim(2) == 42) {
impossible();
} else {
answer({1, 3});
}*/
}
//g++ books.cpp grader.cpp -o books
/*
15 3 42 40
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
*/
