#include <bits/stdc++.h>

#define rep(i,begin,end) for(int i=begin;i<=end;i++)
#define repi(i,end,begin) for(int i=end;i>=begin;i--)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

struct Tree{
	multiset<int> ms;
	multiset<int>::iterator med_it;
	int med_idx;
};

int Ceil(int a, int b){
	return (a+1)/b;
}

void initializeTree(Tree (&tree), int el){
	(tree.ms).insert(el);
	(tree.med_it) = (tree.ms).begin();
	(tree.med_idx) = 1;
}

void TreeInsert(Tree (&tree), int el){
	(tree.ms).insert(el);

	if(el < *(tree.med_it)) (tree.med_idx)++;

	int idx = Ceil((tree.ms).size(),2);

	if(tree.med_idx < idx) (tree.med_it)++;
	else if(tree.med_idx > idx) (tree.med_it)--;

	tree.med_idx = idx;
}

void TreeDelete(Tree (&tree), int el){
	multiset<int>::iterator aux;

	int idx = Ceil((int)(tree.ms).size() - 1,2);

	if(el == *(tree.med_it)){
		aux = (tree.med_it);

		if((tree.med_idx) == idx) aux++;
		else aux--;

		(tree.ms).erase((tree.med_it));
		(tree.med_it) = aux;
	}
	else{
		aux = (tree.ms).find(el);
		(tree.ms).erase(aux);

		if(el < *(tree.med_it)) (tree.med_idx)--;

		if((tree.med_idx) < idx) (tree.med_it)++;
		else if((tree.med_idx) > idx) (tree.med_it)--;
	}

	(tree.med_idx) = idx; 
}

int TreeMerge(Tree (&tree1), Tree (&tree2)){
	multiset<int>::iterator it;

	if((tree1.ms).size() >= (tree2.ms).size()){
		for(it = (tree2.ms).begin(); it != (tree2.ms).end(); it++) TreeInsert(tree1, *it);
		return 1;
	}
	else{
		for(it = (tree1.ms).begin(); it != (tree1.ms).end(); it++) TreeInsert(tree2, *it);
		return 2;
	}
}

int main(){
fio

Tree tree1, tree2;

initializeTree(tree1,9);
initializeTree(tree2,4);

list<Tree> L;

L.push_back(tree1);
L.push_back(tree2);

list<Tree>::iterator L_cur = L.begin(), L_next = L.begin();
L_next++;

multiset<int>::iterator it;

cout << "Items of first tree before merge: ";

for(it = ((*L_cur).ms).begin(); it != ((*L_cur).ms).end(); it++) cout << *it << " ";
cout << '\n';

cout << "Median index for first tree before merge: ";
cout << (*L_cur).med_idx << '\n';

cout << "Median value for first tree before merge: ";
cout << *((*L_cur).med_it) << '\n';

cout << "Items of second list before merge: ";

multiset<int>::iterator it2;

for(it = ((*L_next).ms).begin(); it != ((*L_next).ms).end(); it++) cout << *it << " ";
cout << '\n';

cout << "Median index for second tree before merge: ";
cout << (*L_next).med_idx << '\n';

cout << "Median value for second tree before merge: ";
cout << *((*L_next).med_it) << '\n';

int merge = TreeMerge(*L_cur,*L_next);

cout << "Items of first tree after merge: ";

for(it = ((*L_cur).ms).begin(); it != ((*L_cur).ms).end(); it++) cout << *it << " ";
cout << '\n';

cout << "Median index for first tree after merge: ";
cout << (*L_cur).med_idx << '\n';

cout << "Median value for first tree after merge: ";
cout << *((*L_cur).med_it) << '\n';

cout << "Items of second list after merge: ";

for(it = ((*L_next).ms).begin(); it != ((*L_next).ms).end(); it++) cout << *it << " ";
cout << '\n';

cout << "Median index for second tree after merge: ";
cout << (*L_next).med_idx << '\n';

cout << "Median value for second tree after merge: ";
cout << *((*L_next).med_it) << '\n';
return 0;
}