#include <bits/stdc++.h>
#include "books.h"
using namespace std;
// typedef long long l;
vector<int> get_ans(vector<bool>& in){
vector<int> ans;
for(int i = 0; i < (int)in.size(); i++){
if(in[i]) ans.push_back(i+1);
}
return ans;
}
void solve(int N, int K, long long A, int S) {
vector<long long> v(N, -1);
vector<bool> in(N, 0);
long long sum = 0;
for(int i = 0; i < K; i++){
v[i] = skim(i+1);
in[i] = 1;
sum += v[i];
}
if(sum > 2 * A) {impossible(); return;}
if(sum >= A){
answer(get_ans(in));
return;
}
if(K == N) {impossible(); return;}
int low = 0;
int high = N - 1;
int bst = N;
while(low <= high){
int mid = (low + high) / 2;
if(v[mid] == -1) v[mid] = skim(mid + 1);
if(v[mid] >= A){
bst = mid;
high = mid - 1;
}else low = mid + 1;
}
if(bst != N && bst >= K){
if(sum - v[K - 1] + v[bst] <= 2 * A){
in[K-1] = 0;
in[bst] = 1;
answer(get_ans(in));
return;
}
}
N = bst;
int ind = N - 1;
for(int i = K - 1; i >= 0; i--){
if(v[ind] == -1) v[ind] = skim(ind + 1);
if(sum - v[i] + v[ind] > 2 * A){
int lo = i + 1;
int hi = ind - 1;
sum -= v[i];
in[i] = 0;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(v[mid] == -1) v[mid] = skim(mid + 1);
if(sum + v[mid] >= A && sum + v[mid] <= 2 * A){
in[mid] = 1;
answer(get_ans(in));
return;
}else if(sum + v[mid] < A){
lo = mid + 1;
}else{
hi = mid - 1;
}
}
impossible();
return;
}else{
sum -= v[i];
sum += v[ind];
in[i] = 0;
in[ind] = 1;
if(sum >= A){
answer(get_ans(in));
return;
}
}
ind--;
}
impossible();
}
