#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 1e5 + 10;
ll x[MAXN];
ll get_sum(int m, int k){
ll sum = 0;
for(int i=m; i<=(m + k - 1); i++){
if(!x[i]) x[i] = skim(i);
sum += x[i];
}
return sum;
}
bool check(int m, int k, ll a){
ll sum = 0;
for(int i=(m + k - 1); i>=m; i--){
if(!x[i]) x[i] = skim(i);
sum += x[i];
if(sum > 2 * a) return false;
}
return (sum <= 2 * a);
}
void solve(int n, int k, ll a, int s){
// vou achar o subarray mais para a direita com soma <= 2a
for(int i=1; i<=n; i++) x[i] = 0;
int l = 1, r = n - k + 1;
while(l < r){
int sz = r - l + 1;
int m = l + (r - l + 1) / 2;
if(sz > 20) m = l + rng() % sz;
if(check(m, k, a)) l = m;
else r = m - 1;
}
// cout << l << " " << get_sum(l, k) << endl;
vector<int> ans;
if(a <= get_sum(l, k) && get_sum(l, k) <= 2 * a){
for(int i=l; i<=(l + k - 1); i++) ans.push_back(i);
answer(ans);
return;
}
if(get_sum(l, k) > 2 * a){
impossible();
return;
}
if(l == n - k + 1){
impossible();
return;
}
// entao get_sum(l, k) < a => x[l + k] > a
if(!x[l + k]) x[l + k] = skim(l + k);
if(a <= get_sum(1, k - 1) + x[l + k] && get_sum(1, k - 1) + x[l + k] <= 2 * a){
for(int i=1; i<=(k - 1); i++) ans.push_back(i);
ans.push_back(l + k);
answer(ans);
return;
}
impossible();
}
