#include <bits/stdc++.h>
#include "molecules.h"
using namespace std;
#define pb push_back
#define pi pair<int,int>
#define ll long long
#define mp make_pair
vector<int> find_subset(int l, int u, vector<int> ww) {
int n = ww.size();
vector<ll> w(n);
pi sorted[n];
for(int i =0; i<n ;i++){
w[i] = ww[i];
sorted[i] = {ww[i], i};
}
sort(sorted, sorted + n);
int start = lower_bound(sorted, sorted + n, mp(u + 1, -1)) - sorted;
start--;
set<pair<int, pair<int,int>>> pos;//val, w, ind
vector<bool> nums(1e5 + 5);
int num_ans = -1;
vector<int> ans;
vector<ll> presum(n);
presum[0] = sorted[0].first;
for(int s = 1; s <= start; s++){
presum[s] = presum[s-1] + sorted[s].first;
//cout << s<<": "<<presum[s]<<endl;
}
for(; start >=0; start--){
int i = sorted[start].second;
//if( cursum + weights[i].w > u) continue;
if(w[i] >=l && w[i] <= u){
return vector<int>(1, i);
}
set<int> ins;
bool won = false;
for(pair<int,pair<int,int>> val : pos){
int num = val.first;
if(num + w[i] >= l && num+w[i] <= u){
num_ans = num;
ans.pb(i);
won = true;
break;
}
if(num + w[i] < l ){
ins.insert(num+w[i]);
}
}
if(won ) break;
if(presum[start] + w[i] >= l and !nums[w[i]]){
pos.insert({w[i], {w[i], i}});
nums[w[i]] = true;
}
for(int val : ins){
if(presum[start] + val >= l and !nums[val]){
pos.insert({val, {w[i], i}});
nums[val] = true;
}
}
}
if(num_ans == -1) return vector<int>();
while(num_ans != 0){
pair<int, pi> val = *lower_bound(pos.begin(), pos.end(), mp(num_ans, mp(-1, -1)));
ans.pb(val.second.second);
num_ans = num_ans - val.second.first;
}
sort(ans.begin(), ans.end());
return ans;
}
/***************/
