#include "molecules.h"
#include <bits/stdc++.h>
using namespace std;
long long sumV[200005];
int searchF(int mn, int mx, multiset<pair<long long, int>> &s)
{
auto it=s.lower_bound({mn, 0});
if(it == s.end())
return -1;
if(it->first > mx)
return -1;
return it->second;
}
vector<int> find_subset(int l, int r, vector<int> w)
{
/*
cout<<"got input\n";
cout<<l<<' '<<r<<'\n';
for(int it : w)
cout<<it<<' ';
cout<<"\n\n";
*/
vector<pair<int, int>> v;
for(int i=0; i<(int)w.size();i++)
v.push_back({w[i], i});
sort(v.begin(), v.end());
multiset<pair<long long, int>> s;
sumV[(int)v.size()]=0;
for(int i=(int)v.size()-1; i>=0; i--)
{
sumV[i]=sumV[i+1]+v[i].first;
s.insert(make_pair(sumV[i], i));
}
int id=searchF(l, r, s);
if(id != -1)
{
vector<int> ans;
for(int j=id; j<(int)v.size(); j++)
ans.push_back(v[j].second);
return ans;
}
long long sum=0;
for(int i=0;i<(int)v.size();i++)
{
s.erase(s.find({sumV[i], i}));
sum += v[i].first;
if(sum >= l && sum <= r)
{
vector<int> ans;
for(int j=0;j<=i;j++)
ans.push_back(v[j].second);
return ans;
}
int id=searchF(l-sum, r-sum, s);
if(id != -1)
{
vector<int> ans;
for(int j=0;j<=i;j++)
ans.push_back(v[j].second);
for(int j=id; j<(int)v.size(); j++)
ans.push_back(v[j].second);
return ans;
}
}
vector<int> ans;
return ans;
}
