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