#include <bits/stdc++.h>
#include "books.h"
using namespace std;
//
// --- 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.
//
void solve(int n, int k, long long a, int s) {
#define ull unsigned long long
int l = 1; int r = n;
ull pos = -1;
ull val = -1;
while (l <= r) {
ull mid = (l+r)/2;
ull res = skim(mid);
s--;
if (res > a) {
r = mid - 1;
pos = mid;
val = res;
} else {
l = mid + 1;
}
}
vector <pair<ull,ull>> v;
v.emplace_back(0,0);
for (ull i = 1; i <= k; i++) {
v.emplace_back(skim(i),i);
s--;
}
if (pos != -1) {
ull sum = val;
for (ull i = 1; i <= k-1; i++) sum += v[i].first;
if (a <= sum && sum <= 2*a) {
vector <int> res;
for (ull i = 1; i <= k-1; i++) res.emplace_back(i);
// deb(sum);
// cout << "sum ___ " << sum << endl;
res.emplace_back(pos);
answer(res);
return;
}
} else {
pos = n+1;
}
r = pos-1; l = r-k+1;
l = max(l,k+1);
for (ull i = l; i <= r; i++) {
v.emplace_back(skim(i),i);
s--;
}
// while (s--) skim(1);
for (ull i = 1; i <= k+1; i++) {
l = i; r = i+k-1;
ull sum = 0;
for (ull j = l; j <= r; j++) {
sum += v[j].first;
}
if (a <= sum && sum <= 2*a) {
vector <int> res;
for (ull j = l; j <= r; j++) {
res.emplace_back(v[j].second);
}
// cout << "iii ---" << i << endl;
// cout << "sum ---" << sum << endl;
answer(res);
return;
}
}
impossible();
}
