#include <bits/stdc++.h>
using namespace std;
#include "molecules.h"
#define ll long long
vector<int> indi(vector<ll> &weigh, map<int,vector<int>> &mp) {
vector<int> ind;
for (auto &x:weigh) {
ind.push_back(mp[x].back());mp[x].pop_back();
}
return ind;
}
std::vector<int> find_subset(int l, int u, std::vector<int> w) {
int n=(int)w.size();
map<int,vector<int>> mp;
for (int i=0;i<n;i++) {
mp[w[i]].push_back(i);
}
sort(w.begin(), w.end());
vector<ll> p(n);
p[0]=w[0];
for (int i=1;i<n;i++) {
p[i] = p[i-1]+w[i];
}
if (p[0] > u || p.back() < l) return {};
// check if some prefix becomes possible
for (int i=0;i<n;i++) {
if (l <= p[i] && p[i] <= u) {
vector<ll> we;
for (int j=0;j<=i;j++) we.push_back(w[j]);
return indi(we, mp);
}
}
vector<ll> we;
for (int i=0;p[i]<l && i<n;i++) {
we.push_back(w[i]);
}
int pt = 0, idx = (int)we.size();
ll sum = p[idx-1];
for (int i=idx;i<n;i++) {
sum += w[i] - we[pt];
we[pt] = w[i];
if (l <= sum && sum <= u) return indi(we, mp);
pt++;
pt %= idx;
}
return {};
}
