#include <bits/stdc++.h>
#include "wiring.h"
using ll = long long;
ll myabs(ll x){
if(x<0)return x*(-1);
return x;
}
typedef std::pair<ll,ll> pll;
long long bestcusto(std::vector<int> anl,ll z){
ll best=1e9;
for(auto&x:anl){
best=std::min(best,myabs(x-z));
}
return best;
}
long long min_total_length(std::vector<int> r, std::vector<int> b) {
ll variacao={};
std::vector<pll> alteracoes;
for(auto&x:r)alteracoes.push_back({x,1});
for(auto&x:b)alteracoes.push_back({x,-1});
std::sort(alteracoes.begin(),alteracoes.end());
std::vector<ll> abreb,abrer,fechab,fechar;
ll resp=0;
for(auto&x:alteracoes){
ll cor = x.second,pos=x.first;
if(cor==1){
if(resp<0){
fechar.push_back(pos);
}else abrer.push_back(pos);
resp++;
}else {
if(resp<=0){
abreb.push_back(pos);
}else fechab.push_back(pos);
resp--;
}
}
ll ans=0;
std::sort(abreb.begin(),abreb.end());
std::sort(abrer.begin(),abrer.end());
std::sort(fechab.begin(),fechab.end());
std::sort(fechar.begin(),fechar.end());
{
std::vector<pll> penalidades;
ll dif = myabs(r.size()-b.size());
if(resp>0){///Quantidade maior de vermelhos
assert(abrer.size()>fechab.size());
/// std::cout<<abrer.size()<<" "<<fechab.size()<<":\n";
for(auto&x:abrer){
penalidades.push_back({bestcusto(b,x)-x,x});
}
std::sort(penalidades.begin(),penalidades.end());
/// std::cout<<dif<<" "<<penalidades.size()<<"<-\n";
for(int i=0;i<dif;++i){
ans+=bestcusto(b,penalidades[i].second);
/// std::cout<<"Remove "<<penalidades[i].second<<" "<< bestcusto(b,penalidades[i].second)<<" "<<ans<<"\n";
}
abrer.clear();
for(int i=dif;i<penalidades.size();++i){
abrer.push_back(penalidades[i].second);
}
/// std::cout<<"Nov: "<<abreb.size()<<" "<<penalidades.size()<<"\n";
}else if(resp<0){
assert(abreb.size()>fechar.size());
/// std::cout<<abreb.size()<<" "<<fechar.size()<<":\n";
for(auto&x:abreb){
penalidades.push_back({bestcusto(r,x)-x,x});
}
std::sort(penalidades.begin(),penalidades.end());
/// std::cout<<dif<<" "<<penalidades.size()<<"<-\n";
for(int i=0;i<dif;++i){
ans+=bestcusto(r,penalidades[i].second);
/// std::cout<<"Remove "<<penalidades[i].second<<" "<< bestcusto(r,penalidades[i].second)<<" "<<ans<<"\n";
}
abreb.clear();
for(int i=dif;i<penalidades.size();++i){
abreb.push_back(penalidades[i].second);
}
/// std::cout<<"Nov: "<<abreb.size()<<" "<<penalidades.size()<<"\n";
}
}
std::cout<<ans<<"!\n";
std::sort(abreb.begin(),abreb.end());
std::sort(abrer.begin(),abrer.end());
std::sort(fechab.begin(),fechab.end());
std::sort(fechar.begin(),fechar.end());
///Abre B com Fecha R
{
std::cout<<abreb.size()<<" "<<fechar.size()<<"\n";
ll somab=0,somar=0;
for(auto&x:abreb)somab+=x;
for(auto&x:abreb)std::cout<<x<<" ";std::cout<<"\n";
for(auto&x:fechar)somar+=x;
for(auto&x:fechar)std::cout<<x<<" ";std::cout<<"\n";
ll dif = myabs(abreb.size()-fechar.size());
ans+=somar-somab;
///Proxima etapa: guloso retirando conexoes
std::deque<ll> aa,ba;
for(auto&x:abreb){
aa.push_back(x+bestcusto(r,x));
}
for(auto&x:fechar){
ba.push_back(bestcusto(b,x)-x);
}
std::sort(aa.begin(),aa.end());
std::sort(ba.begin(),ba.end());
for(int i=0;i!=aa.size();++i){
if(aa[i]+ba[i]<0)ans+=aa[i]+ba[i];
}
}
std::cout<<ans<<"!\n";
///Abre R com Fecha B
{
std::cout<<abrer.size()<<" "<<fechab.size()<<"\n";
ll somab=0,somar=0;
for(auto&x:abrer)somar+=x;
for(auto&x:abrer)std::cout<<x<<" ";std::cout<<"\n";
for(auto&x:fechab)somab+=x;
for(auto&x:fechab)std::cout<<x<<" ";std::cout<<"\n";
ll dif = myabs(abrer.size()-fechab.size());
ans+=somab-somar;
///Proxima etapa: guloso retirando conexoes
std::deque<ll> aa,ba;
for(auto&x:abrer){
aa.push_back(x+bestcusto(b,x));
}
for(auto&x:fechab){
ba.push_back(bestcusto(r,x)-x);
}
std::sort(aa.begin(),aa.end());
std::sort(ba.begin(),ba.end());
for(int i=0;i!=aa.size();++i){
if(aa[i]+ba[i]<0)ans+=aa[i]+ba[i];
}
}
std::cout<<ans<<"!\n";
return ans;
}
