//#include "grader.cpp"
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
//
// --- 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 a[100007];
vector < int > get (int l, int r){
vector < int > ret;
for (int i = l; i <= r; i++)
ret.pb(i);
return ret;
}
void solve(int N, int K, long long A, int S) {
int l = 1, r = N, s = 0, k = K;
ll rs = 0;
while (l + 1 < r){
int mid = (l + r) >> 1;
a[mid] = skim(mid);
// S--;
if (a[mid] * 1LL * K > 2LL * A){
r = mid;
}
else if (a[mid] * 1LL * K < A){
l = mid;
}
else {
s = mid;
break;
}
}
if (!s)
s = l;
l = max(1, s - k + 1);
r = min(N, s + k - 1);
for (int i = l; i <= r; i++){
if (!a[i])
a[i] = skim(i);
}
for (int i = 1; i < k; i++){
if (!a[i])
a[i] = skim(i);
}
for (int i = l; i < l + k; i++)
rs += a[i];
if (rs >= A && rs <= 2 * A){
answer(get(l, l + k - 1));
return;
}
int it = 0;
for (int i = l + k; i <= r; i++){
rs -= a[i - k];
rs += a[i];
if (rs >= A){
it = i;
break;
}
}
if (rs >= A && rs <= 2 * A){
answer(get(it - k + 1, it));
return;
}
vector < int > ret;
rs = a[it];
for (int i = 1; i < k; i++)
rs += a[i];
if (rs >= A && rs <= 2 * A){
ret = get(1, k - 1);
ret.pb(it);
answer(ret);
return;
}
impossible();
return;
}
