#include <bits/stdc++.h>
#include "books.h"
using namespace std;
const int MAX = 1e5 + 10 ;
long long arr[MAX] ;
long long query(int idx)
{
if(arr[idx] == -1)
arr[idx] = skim(idx) ;
return arr[idx] ;
}
void solve(int n, int k, long long a, int s)
{
memset(arr , -1 , sizeof(arr)) ;
long long sum = 0 ;
for(int i = 1 ; i <= k-1 ; ++i)
arr[i] = skim(i) , sum += arr[i] ;
int l = k , r = n ;
int idx = l ;
while(l <= r)
{
int mid = (l + r) >> 1 ;
if(sum + query(mid) <= 2 * a)
idx = mid , l = mid+1 ;
else
r = mid-1 ;
}
query(idx) ;
sum += arr[idx] ;
if(sum > 2*a)
{
impossible() ;
return ;
}
else if(sum >= a)
{
vector<int>ans ;
for(int i = 1 ; i <= k-1 ; ++i)
ans.push_back(i) ;
ans.push_back(idx) ;
answer(ans) ;
return ;
}
int cur = k-1 ;
for(int i = idx-1 ; i >= 1 ; --i)
{
sum += query(i) ;
sum -= query(cur) , --cur ;
assert(sum <= 2*a) ;
if(sum >= a)
{
vector<int>ans ;
for(int j = 1 ; j <= cur ; ++j)
ans.push_back(i) ;
for(int j = i ; j <= idx ; ++j)
ans.push_back(j) ;
answer(ans) ;
return ;
}
}
impossible() ;
return ;
}
