#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.
//
const int MAXN = 112345;
long long qr[MAXN];
long long val(int a) {
if(qr[a] == -1) qr[a] = skim(a);
return qr[a];
}
long long ts(int a, int b, int c, int d) {
long long tst = 0;
for(int i = a; i <= b; i++) tst += qr[i];
for(int i = c; i <= d; i++) tst += qr[i];
return tst;
}
void solve(int n, int k, long long a, int s) {
// TODO implement this function
for(int i = 1; i <= n; i++) qr[i] = -1;
int ini = 1, fim = n;
while(ini < fim) {
int m = (ini + fim) / 2;
//if(ini == fim - 1) m = fim;
if(val(m) >= a) fim = m;
else ini = m + 1;
}
long long vlm = val(ini);
if(val(fim) < a) {
fim++;
ini++;
vlm = 1123456789012345678;
}
if(ts(1, k, 0, -1) >= 2 * a) impossible();
else if(ts(1, k, 0, -1) >= a) {
vector <int> temp;
for(int i = 1; i <= k; i++) temp.push_back(i);
answer(temp);
}
if(ts(1, k - 1, 0, -1) + vlm <= 2 * a) {
vector <int> temp;
for(int i = 1; i < k; i++) temp.push_back(i);
temp.push_back(ini);
answer(temp);
}
if(ini - 1 < k) impossible();
for(int i = 0; i <= k; i++) {
if(ini - k + 1 < 1) continue;
if(ts(1, i, ini - k + i, ini - 1) <= 2 * a && ts(1, i, ini - k + i, ini - 1) >= a) {
vector <int> temp;
for(int j = 1; j <= i; j++) temp.push_back(j);
for(int j = ini - k + i; j < ini; j++) temp.push_back(j);
answer(temp);
}
}
impossible();
}
