#include "books.h"
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef ll itn;
#define ff first
#define ss second
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 32768;
const ll NNN = 100007;
ll n, k, a, s;
ll p[100007];
void ansfrom(int st) {
vector<int>v;
for (int i = st; i < st + k; i++) {
v.push_back(i + 1);
}
answer(v);
exit(0);
}
void check(ll sum, int st) {
if (sum >= a && sum <= 2 * a)ansfrom(st);
}
ll skimm(int ind) {
if (p[ind] != -1)return p[ind];
return p[ind] = skim(ind);
}
ll sum_from(int ind) {
ll res = 0;
for (int i = ind; i < ind + k; i++) {
res += skimm(i);
}
return res;
}
void solve(int N, int K, long long A, int S) {
n = N;
k = K;
a = A;
s = S;
if (n == s) {
ll sum = 0;
ll least = -1;
for (int i = 0; i < n; i++) {
p[i] = skim(i + 1);
if (i < k - 1)sum += p[i];
else if (p[i] > a && least == -1)least = i;
}
if (least != -1 && sum + p[least] >= a && sum + p[least] <= 2 * a) {
vector<int>v;
for (int i = 0; i < k - 1; i++) {
v.push_back(i + 1);
}
v.push_back(least + 1);
answer(v);
return;
}
else {
sum += p[k - 1];
check(sum, 0);
for (int i = k; i < n; i++) {
sum -= p[i - k];
sum += p[i];
check(sum, i - k + 1);
}
impossible();
return;
}
}
else if (s >= 170) {
ll sum = 0;
vector<int>v;
for (int i = 1; i <= n; i++) {
p[i] = -1;
}
for (int i = 0; i < k - 1; i++) {
sum += skimm(i + 1);
v.push_back(i + 1);
}
if (sum + skimm(k) > 2 * a || sum + skimm(n) < a) {
impossible();
return;
}
int l = k, r = n;
while (l < r) {
int m = (l + r) / 2;
if (skimm(m) >= a) {
r = m;
}
else {
l = m + 1;
}
}
ll val = sum + skimm(l);
if (val >= a && val <= 2 * a) {
v.push_back(l);
answer(v);
return;
}
l = 1, r = n - k;
while (l < r) {
int mid = (l + r) / 2;
sum = sum_from(mid);
if (a <= sum && sum <= 2 * a) {
ansfrom(mid);
}
else if (a > sum) {
l = mid + 1;
}
else {
r = mid;
}
}
sum = sum_from(l);
if (a <= sum && sum <= 2 * a) {
ansfrom(l);
}
impossible();
return;
}
}
