#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <tuple>

using std::set;
using std::vector;
using std::cin;
using std::cout;
using std::string;

const set<int> universum = []() {// Заполнение Универсального множества
	set<int> result;//создаем пустое множество
	for (int i = 1; i <= 35; i++) {// берем элементы от 1-35
		result.insert(i);//записываем элементы
	}
return result;
}();

void FillSet(set<int>& s, int n) {//заполняет множество значениями, введенными с клавиатуры
	for (int i = 0; i < n; i++) {//
		int temp;
		cin >> temp;//Принимает значение элемента
		s.insert(temp);//записывает значение
	}
}

set<int> Union(const set<int>& first, const set<int>& second) {//операция объединения
	set<int> result;//создаем пустое множество С
	for (const auto& x : first) {//берем эдементы множества А
		result.insert(x);//записываем элементы множестав А в множество С
	}
	for (const auto& y : first) {//1
		for (const auto& x : second) {//2
			if (x != y) {//сравниваем первый элемент множества А с элементом множества В
				result.insert(x);//если не равен(если равен, то идем в пункт 2), то добавляем в множество С, если равен, то переходим в пункт 1 и берем следующий элемент А
			}
		}
	}
	return result;
}

set<int> Intersection(const set<int>& first, const set<int>& second) {//операция пересечения
	set<int> result;//создаем пустое множество
	for (const auto& item_first : first) {//1
		for (const auto& item_second : second) {//2
			if (item_first == item_second) {//сравниваем первый элемент множества А с элементом множества В
				result.insert(item_first);//если равен(если не равен, то идем в пункт 2), то добавляем в множество С, переходим в пункт 1 и берем следующий элемент А
			}
		}
	}
	return result;
}

set<int> Difference(const set<int>& first, const set<int>& second) {// Операция разности
	set<int> result;//создаем пустое множество
	for (const auto& item_first : first) {// Берем элемент мн-ва А
		auto it=std::find(second.begin(), second.end(), item_first);//Берем элемент мн-ва В и сравниваем с элементом мн-ва А
		if (it == second.end()) {//Если данного эл-та нету в мн-ве С, то записываем его
			result.insert(item_first);
		}
	}
	return result;
}

set<int> Addition(const set<int>& first){ //Операция дополнения
	return Difference(universum,first);//Берем разность между Универсумом и мн-вом
}

set<int> SymmetryDifference(const set<int>& first, const set<int>& second) {//Операция Симм. разности
	set<int> result(Difference(first, second)); //записываем во мн-во С разность между мн-вами А и В
	for (const auto& x : Difference(second, first)) {          // записываем во мн-во С разность между мн-вами В и А
		result.insert(x);
	}
	return result;
}

set<std::pair<int, int>> Cartesian(const set<int>& first, const set<int>& second) {//Операция Декартова произведения
	set<std::pair<int, int>> result;//создаем пустое множество
	for (const auto& first_it : first) {//Берем последовательно элементы множества А
		for (const auto& second_it : second) {//Берем последовательно элементы множества А
			result.insert(std::make_pair(first_it, second_it));//создаем кортеж <A,B>
		}
	}
	return result;

}


std::ostream& operator<<(std::ostream& out, const set<int>& s) {
	out << "{";
	if (s.size() == 0) {
		out << "}";
		return out;
	}
	for (auto it = s.begin(); it != s.end(); it++) {
		if (it != prev(s.end())) {
			out << *it << ", ";
		}
		else {
			out << *it << "}";
		}
	}
	return out;
}

std::ostream& operator<<(std::ostream& out, const set<std::pair<int, int>>& s) { // Обращение к элементам множества А и В, для вывода кортежа
	out << "{";
	if (s.size() == 0) {
		out << "}";
		return out;
	}
	for (auto it = s.begin(); it != s.end(); it++) {

		if (it != prev(s.end())) {
			out <<"<" <<it->first << ", "<<it->second<<">, " ;
		}
		else {
			out << "<" << it->first << ", " << it->second << ">}";
		}
	}
	return out;
}

void Menu() {//выбор операции
	cout << "1 - выводит объединение множеств" << std::endl << "2 - выводит пересечения множеств" << std::endl
		<<"3 - выводит разность множеств"<<std::endl
		<<"4 - выводит симметрическую разность"<<std::endl
		<< "5 - выводит дополнения множества" << std::endl
		<< "6 - выводит декартово произведение" << std::endl
		<< "7 - выйти из программы" << std::endl;
}

void DefaultFill( set<int>& first, set<int>& second,int first_size,int second_size) {
	for (int i = 1; i <= first_size; i++) {//Заполняем множество А методом высказывания А = {𝑥∈𝑁 | 𝑥=𝑘∗2, 𝑘=1,𝑛} , где n – мощность множества А.
		first.insert(2*i );//Добавляем элемент во множество
	}
	for (int i = 1; i <= second_size; i++) {//Заполняем множество В методом высказывания В ={𝑦∈𝑁 |𝑦=(𝑘+1)∗2, 𝑘= 1,𝑔} , где g – мощность множества В.
		second.insert((i+1)*2);//Добавляем элемент во множество
	}
}

int main() {
	setlocale(LC_ALL, "ru");
	set<int> first, second;//создаем пустые множества А и В
	int first_amount, second_amount;
	cout << "Введите размер множеств\n";
	cin >> first_amount >> second_amount;//Вводим размеры множеств А и В
	int command=0;
	do {
		cout << "Введите номер команды\n1.Задание множество методом перечисления\n2.Задание множество методом высказивание\n";
		cin >> command;
		switch (command) {//Выбор операция задания множеств
		case 1: {//Перечисление
			cout << "Введите элементы первого множетсва\n";
			FillSet(first, first_amount);
			cout << "Введите элементы второго множетсва\n";
			FillSet(second, second_amount);
			break;
		}
		case 2: {//Высказывание
			DefaultFill(first,second,first_amount,second_amount);
			cout << first << std::endl << second << std::endl;
			break;
		}
		default: {
			cout << "Неправильная команда\n";
			break;
		}
		}
	} while ((command!=1) && (command !=2));

	while (true) {
		Menu();//Перечисление всех операций
		cout << "Введите номер команды\n";
		int number;
		cin >> number;
		switch (number)//Выбор операции
		{
		case 1: {//операция объединения
			cout <<"Объединение двух множеств: "<< Union(first, second) << std::endl;
			break;
		}
		case 2: {//операция пересечения
			cout <<"Пересечение двух множеств: "<< Intersection(first, second) << std::endl;
			break;
		}
		case 3: {//операция разности
			int k;
			cout << "Введите номер операции\n1. Операция разности между множествами А и В (А\\В)\n2. Операция разности между множествами B и A (B\\A)\n";
			cin >> k;
			switch (k)//Выбор операций
			{
			case 1: {
				cout <<"Разность  множества A и B: "<< Difference(first, second) << std::endl;
				break;
			}
			case 2: {
				cout << "Разность  множества B и A: " << Difference(second, first) << std::endl;
				break;
			}
			default:
				break;
			}

			break;
		}
		case 4: {//операция симметрической разности
			cout <<"Симметрическая разность: "<<SymmetryDifference(first,second)<< std::endl;
			break;
		}

		case 5: {//операция дополнения
			int k;
			cout << "Введите номер множества\n";
			cin >> k;
			switch (k)
			{
			case 1: {
				cout <<"Дополнение множества A: "<<Addition(first) << std::endl;
				break;
			}
			case 2: {
				cout << "Дополнение множества B: " << Addition(second) << std::endl;
				break;
			}
			default:
				break;
			}

			break;
		}
		case 6: {//операция декартово произведение
			int k;
			cout << "Введите номер операции\n1. Декартово произведение множеств А и В (А x B)\n2. Декартово произведение множеств B и A (B x A)\n";
			cin >> k;
			switch (k)
			{
			case 1: {
				cout << "Декартово произведение множеств А и В(А x B): " << Cartesian(first,second) << std::endl;
				break;
			}
			case 2: {
				cout <<"Декартово произведение множеств B и A(B x A): "<< Cartesian(second,first) << std::endl;
				break;
			}
			default:
				break;
			}
			break;

		}
		case 7: {//операция выхода
			return 0;
		}
		default: {
			cout << "Вы ввели неправильную команду\n";
			break;
		}
		}
	}
}