#include <bits/stdc++.h>
#include "books.h"
using namespace std;
void solve(int n, int k, long long goal, int s){
int lo = 0, hi = n-1, pos;
while(lo < hi){
int mid = lo+(hi-lo)/2;
long long val = skim(mid+1);
if(val >= goal) hi = mid;
else lo = mid+1;
}
pos = lo; long long val = skim(pos+1);
if(val < goal) pos = n;
vector<int> ans;
vector<long long> arr(n, 0);
if(pos < k-1){
impossible();
return;
}
if(pos != n){
long long sum = 0;
for(int i = 0; i<k-1; i++) sum += (arr[i] ? arr[i] : arr[i] = skim(i+1));
if(goal <= sum+val && sum+val <= 2ll*goal){
for(int i = 0; i<k-1; i++) ans.push_back(i+1);
ans.push_back(pos+1);
answer(ans);
return;
}
if(pos == k-1){
impossible();
return;
}
}
for(int i = 0; i<k; i++) arr[i] = (arr[i] != 0 ? arr[i] : arr[i] = skim(i+1));
for(int i = pos-1; i>=pos-k; i--) arr[i] = (arr[i] != 0 ? arr[i] : arr[i] = skim(i+1));
for(int i = 0; i<=k; i++){
long long sum = 0;
for(int j = 0; j<i; j++) sum += arr[j];
for(int j = pos-1; j>=pos-(k-i); j--) sum += arr[j];
if(goal <= sum && sum <= 2ll*goal){
for(int j = 0; j<i; j++) ans.push_back(j+1);
for(int j = pos-1; j>=pos-(k-i); j--) ans.push_back(j+1);
answer(ans);
return;
}
}
impossible();
}
