#include <bits/stdc++.h>
#include "books.h"
#define sz(x) (int)(x.size())
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.
//
map<int, long long> mp ;
long long A ;
long long ask(int x)
{
if(mp.find(x) != mp.end()) return mp[x] ;
return mp[x] = skim(x) ;
}
bool check(long long s) { return s >= A && s <= A+A ;}
void solve(int N, int K, long long a, int S)
{
A = a ;
int l = 1, r = N , mid , best = -1 ;
while( l <= r )
{
mid = (l+r)>>1 ;
if( ask(mid) <= A ) { best = mid ; l = mid+1 ; }
else r = mid-1 ;
}
if( best == -1 ) impossible() ;
vector<long long> v ;
vector<int> R ;
if( best <= 2*K )
{
for(int i = 1 ; i <= best; i++ )
{
v.push_back(ask(i)) ;
R.push_back(i) ;
}
}
else
{
for(int i = 1 ; i <= K ; i++ ) v.push_back(ask(i)) , R.push_back(i) ;
for(int i = best-K+1 ; i <= best ; i++ ) v.push_back(ask(i)) , R.push_back(i) ;
}
if(best+1 <= N && best >= K-1)
{
long long s = ask(best+1) ;
for(int i = 0 ; i < K-1 ; i++ ) s += v[i] ;
if( check(s) )
{
vector<int> ans = {best+1} ;
for(int i = 1 ; i < K ; i++ ) ans.push_back(i) ;
answer(ans) ;
return ;
}
}
if( best < K ) impossible() ;
long long s = 0 ;
for(int i = 0 ; i < K ; i++ ) s += v[i] ;
if( check(s) )
{
vector<int> ans ;
for(int i = 0 ; i < K ; i++ ) ans.push_back(R[i]) ;
answer(ans) ;
return ;
}
for(int i = K ; i < sz(v) ; i++ )
{
s -= v[i-K] ;
s += v[i] ;
if(check(s))
{
vector<int> ans ;
for(int j = i-K+1 ; j <= i ; j++ ) ans.push_back(R[j]) ;
answer(ans) ;
return ;
}
}
impossible() ;
}
