#include "books.h"
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
/*
Binary search for first book i >= A.
Answer is either this book + first K-1 books, or a subset of (first K books + last K books before i)
*/
//books, choice size, limit, skim limit
void solve(int N, int K, long long A, int S)
{
vector<long long> difficulty(N+1, -1);
int bigbook_low = 1, bigbook_high = N;
while(bigbook_low != bigbook_high)
{
int m = (bigbook_low + bigbook_high)/2;
if(skim(m) < A) bigbook_low = m+1;
else bigbook_high = m;
}
int bigbook = bigbook_low;
set<int> potential_books_set;
for(int i = 1; i <= K; i++)
potential_books_set.insert(i);
for(int i = max(1, bigbook - K); i <= bigbook; i++)
potential_books_set.insert(i);
vector<int> potential_books;
for(int b: potential_books_set)
potential_books.push_back(b);
int X = potential_books.size();
for(int b: potential_books)
difficulty[b] = skim(b);
for(int mask = 0; mask < (1 << X); mask++)
{
int ct1 = 0;
for(int i = 0; i < X; i++)
if(mask & (1 << i))
ct1++;
if(ct1 != K) continue;
long long sm = 0;
for(int i = 0; i < X; i++)
if(mask & (1 << i))
sm += difficulty[potential_books[i]];
if(A <= sm && sm <= 2*A)
{
vector<int> res;
for(int i = 0; i < X; i++)
if(mask & (1 << i))
res.push_back(potential_books[i]);
answer(res);
}
}
impossible();
}
