#include <iostream>
#include <string>
 
using namespace std;
 
 
//Объявление класса "Множество":
template <class T>
class set
{
public:
        T *a;
        int max_size;
        int size;
public:
        //Конструкторы:
        set(int maxim);
        set(set <T> &x);
 
        //Деструктор:
        ~set();
 
        void add(T x);//добавление эл-та в множество
        bool check_in(T x);//проверка вхождения эл-та в множество
 
        void output();//Вывод множества на экран
        set<T> operator= (const set <T> &s);//операция: присвоение одного множества другому
        set<T> operator* (set <T> &s2);//операция: пересечение двух множеств
 
 
};
 
 
void menu();
 
int main()
{
        setlocale(LC_ALL, "Russian");
        cout << "Добро пожаловать в программу!" << endl;
        menu();
 
        return 0;
}
 
 
void menu()
{
        bool p1, p2; p1 = p2 = true;
        char n;
        char choose;
        int max_1, max_2;
        cout << "Введите максимальный размер первого множества: ";
        cin >> max_1;
        cout << "Введите максимальный размер второго множества: ";
        cin >> max_2;
        set <int> set1(max_1);
        set <int> set2(max_2);
        set <int> set3(std::min(max_1,max_2));
 
 
        int x;
        do {
                cout << '\n'
                        << "Меню:"
                        << '\n' << "1. Добавление эл-та в множество"
 
                        << '\n' << "5. Пересечение двух множеств"
 
                        << '\n' << "0. Выход"
                        << '\n' << "<";
                cin >> n;
                //system("cls");
                switch (n)
                {
 
                case '1':cout << "Выберите множество для добавления (1 или 2): ";
                        cin >> choose;
 
                        if (choose == '1')
                        {
                                if (p1 == true)
                                {
                                        for (int i = 0; i < max_1; i++)
                                        {
                                                cout << "Введите э-т: ";
                                                cin >> x;
                                                set1.add(x);
                                        }
                                        cout << "Получившееся множество 1" << endl;
                                        set1.output();
                                        cout << " " << endl;
                                        p1 = false;
                                }
                                else { cout << "Вы уже ввели множество 1" << endl; set1.output(); }
                        }
                        if (choose == '2')
                        {
                                if (p2 == true){
                                        for (int i = 0; i < max_2; i++)
                                        {
                                                cout << "Введите э-т: ";
                                                cin >> x;
                                                set2.add(x);
                                        }
                                        cout << "Получившееся множество 2" << endl;
                                        set2.output();
                                        cout << " " << endl;
                                        p2 = false;
                                }
                                else { cout << "Вы уже ввели множество 2" << endl; set2.output(); }
                        }
 
                        break;
 
 
                case '5':set3 = (set1*set2);
                        cout << "Исходное множество 1" << endl;
                        set1.output();
                        cout << "Исходное множество 2" << endl;
                        set2.output();
                        cout << "Получившееся множество 3" << endl;
                        set3.output();
                        cout << " " << endl;
                        break;
 
 
 
                case '0':return;
                default:cout << "Действие не выбрано";
                }
        } while (true);
 
 
}
template <class T>
bool set <T>::check_in(T x)
{
        for (int i = 0; i<size; i++)
        if (a[i] == x)
                return true;
        return false;
}
template <class T>
void set<T> ::add(T x)
{
        if (size<max_size)
        {
                if (!check_in(x))
                {
                        a[size] = x;
                        size += 1;
                        cout << "Добавление прошло успешно" << endl;
                }
                else
                {
                        cout << "Добавление невозможно!!!" << endl;
                        cout << "Одинаковые элементы содержаться в множестве только один раз!!!" << endl;
                }
        }
        else
        {
                cout << "Добавление невозможно" << endl;
                cout << "Размер множества не соответствует количеству элементов!!!" << endl;
        }
}
template <class T>
void set<T>::output()
{
        if (size == 0)
        {
                cout << "{}";
                return;
        }
        cout << "{" << a[0];
        for (int i = 1; i<size; i++)
                cout << ", " << a[i];
        cout << "}" << endl;
 
}
 
 
 
 
 
template <class T>
set<T> set<T>:: operator* (  set <T> &s2)
{
        int k;
        k = 0;
        set <T> s(max_size);
        s.size = 0;
        for (int i = 0; i < size; i++)
                cout << a[i] <<  " ";
        cout << endl;
        for (int j = 0; j < s2.size; j++)
                cout <<  s2.a[j] << " ";
        cout << endl;
        for (int i = 0; i < size; i++)
        {
                for (int j = 0; j < s2.size; j++)
                if (s2.a[j] == a[i])
                {
 
                        s.a[k] = s2.a[j];
                        k++;
                        s.size += 1;
                }
        }
 
        return s;
}
 
 
 
 
 
template <class T>
set<T> set<T>:: operator= (const set <T> &s)
{
        if (this == &s)
                return *this;
        if (max_size != s.max_size)
        {
                delete[]a;
                a = new T[s.max_size];
                size = 0;
                max_size = s.max_size;
        }
        for (int i = 0; i<max_size; i++)
        {
                a[i] = s.a[i];
        }
        size = s.size;
        return *this;
}
 
 
 
 
 
 
 
template <class T>
set<T>::set(int maxim)
{
        a = new T[maxim];
        for (int i = 0; i<maxim; i++)
                a[i] = 0;
        max_size = maxim;
        size = 0;
}
 
 
template <class T>
set<T>::set(set<T> &x)
{
        max_size = x.max_size;
        a = new T[max_size];
        for (int i = 0; i<max_size; i++)
                a[i] = x.a[i];
}
 
 
template <class T>
set<T>::~set()
{
        delete[]a;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgogCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKIAovL9Ce0LHRitGP0LLQu9C10L3QuNC1INC60LvQsNGB0YHQsCAi0JzQvdC+0LbQtdGB0YLQstC+IjoKdGVtcGxhdGUgPGNsYXNzIFQ+CmNsYXNzIHNldAp7CnB1YmxpYzoKICAgICAgICBUICphOwogICAgICAgIGludCBtYXhfc2l6ZTsKICAgICAgICBpbnQgc2l6ZTsKcHVibGljOgogICAgICAgIC8v0JrQvtC90YHRgtGA0YPQutGC0L7RgNGLOgogICAgICAgIHNldChpbnQgbWF4aW0pOwogICAgICAgIHNldChzZXQgPFQ+ICZ4KTsKIAogICAgICAgIC8v0JTQtdGB0YLRgNGD0LrRgtC+0YA6CiAgICAgICAgfnNldCgpOwogCiAgICAgICAgdm9pZCBhZGQoVCB4KTsvL9C00L7QsdCw0LLQu9C10L3QuNC1INGN0Lst0YLQsCDQsiDQvNC90L7QttC10YHRgtCy0L4KICAgICAgICBib29sIGNoZWNrX2luKFQgeCk7Ly/Qv9GA0L7QstC10YDQutCwINCy0YXQvtC20LTQtdC90LjRjyDRjdC7LdGC0LAg0LIg0LzQvdC+0LbQtdGB0YLQstC+CiAgICAgICAgIAogICAgICAgIHZvaWQgb3V0cHV0KCk7Ly/QktGL0LLQvtC0INC80L3QvtC20LXRgdGC0LLQsCDQvdCwINGN0LrRgNCw0L0KICAgICAgICBzZXQ8VD4gb3BlcmF0b3I9IChjb25zdCBzZXQgPFQ+ICZzKTsvL9C+0L/QtdGA0LDRhtC40Y86INC/0YDQuNGB0LLQvtC10L3QuNC1INC+0LTQvdC+0LPQviDQvNC90L7QttC10YHRgtCy0LAg0LTRgNGD0LPQvtC80YMKICAgICAgICBzZXQ8VD4gb3BlcmF0b3IqIChzZXQgPFQ+ICZzMik7Ly/QvtC/0LXRgNCw0YbQuNGPOiDQv9C10YDQtdGB0LXRh9C10L3QuNC1INC00LLRg9GFINC80L3QvtC20LXRgdGC0LIKICAgICAgICAgCiAKfTsKIAogCnZvaWQgbWVudSgpOwogCmludCBtYWluKCkKewogICAgICAgIHNldGxvY2FsZShMQ19BTEwsICJSdXNzaWFuIik7CiAgICAgICAgY291dCA8PCAi0JTQvtCx0YDQviDQv9C+0LbQsNC70L7QstCw0YLRjCDQsiDQv9GA0L7Qs9GA0LDQvNC80YMhIiA8PCBlbmRsOwogICAgICAgIG1lbnUoKTsKICAgICAgICAKICAgICAgICByZXR1cm4gMDsKfQogCiAKdm9pZCBtZW51KCkKewogICAgICAgIGJvb2wgcDEsIHAyOyBwMSA9IHAyID0gdHJ1ZTsKICAgICAgICBjaGFyIG47CiAgICAgICAgY2hhciBjaG9vc2U7CiAgICAgICAgaW50IG1heF8xLCBtYXhfMjsKICAgICAgICBjb3V0IDw8ICLQktCy0LXQtNC40YLQtSDQvNCw0LrRgdC40LzQsNC70YzQvdGL0Lkg0YDQsNC30LzQtdGAINC/0LXRgNCy0L7Qs9C+INC80L3QvtC20LXRgdGC0LLQsDogIjsKICAgICAgICBjaW4gPj4gbWF4XzE7CiAgICAgICAgY291dCA8PCAi0JLQstC10LTQuNGC0LUg0LzQsNC60YHQuNC80LDQu9GM0L3Ri9C5INGA0LDQt9C80LXRgCDQstGC0L7RgNC+0LPQviDQvNC90L7QttC10YHRgtCy0LA6ICI7CiAgICAgICAgY2luID4+IG1heF8yOwogICAgICAgIHNldCA8aW50PiBzZXQxKG1heF8xKTsKICAgICAgICBzZXQgPGludD4gc2V0MihtYXhfMik7CiAgICAgICAgc2V0IDxpbnQ+IHNldDMoc3RkOjptaW4obWF4XzEsbWF4XzIpKTsKICAgICAgICAKICAgICAgICAKICAgICAgICBpbnQgeDsKICAgICAgICBkbyB7CiAgICAgICAgICAgICAgICBjb3V0IDw8ICdcbicKICAgICAgICAgICAgICAgICAgICAgICAgPDwgItCc0LXQvdGOOiIKICAgICAgICAgICAgICAgICAgICAgICAgPDwgJ1xuJyA8PCAiMS4g0JTQvtCx0LDQstC70LXQvdC40LUg0Y3Quy3RgtCwINCyINC80L3QvtC20LXRgdGC0LLQviIKICAgICAgICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICAgICAgICA8PCAnXG4nIDw8ICI1LiDQn9C10YDQtdGB0LXRh9C10L3QuNC1INC00LLRg9GFINC80L3QvtC20LXRgdGC0LIiCiAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAgPDwgJ1xuJyA8PCAiMC4g0JLRi9GF0L7QtCIKICAgICAgICAgICAgICAgICAgICAgICAgPDwgJ1xuJyA8PCAiPCI7CiAgICAgICAgICAgICAgICBjaW4gPj4gbjsKICAgICAgICAgICAgICAgIC8vc3lzdGVtKCJjbHMiKTsKICAgICAgICAgICAgICAgIHN3aXRjaCAobikKICAgICAgICAgICAgICAgIHsKIAogICAgICAgICAgICAgICAgY2FzZSAnMSc6Y291dCA8PCAi0JLRi9Cx0LXRgNC40YLQtSDQvNC90L7QttC10YHRgtCy0L4g0LTQu9GPINC00L7QsdCw0LLQu9C10L3QuNGPICgxINC40LvQuCAyKTogIjsKICAgICAgICAgICAgICAgICAgICAgICAgY2luID4+IGNob29zZTsKIAogICAgICAgICAgICAgICAgICAgICAgICBpZiAoY2hvb3NlID09ICcxJykKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIChwMSA9PSB0cnVlKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbWF4XzE7IGkrKykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY291dCA8PCAi0JLQstC10LTQuNGC0LUg0Y0t0YI6ICI7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNpbiA+PiB4OwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzZXQxLmFkZCh4KTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvdXQgPDwgItCf0L7Qu9GD0YfQuNCy0YjQtdC10YHRjyDQvNC90L7QttC10YHRgtCy0L4gMSIgPDwgZW5kbDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNldDEub3V0cHV0KCk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICIgIiA8PCBlbmRsOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcDEgPSBmYWxzZTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZWxzZSB7IGNvdXQgPDwgItCS0Ysg0YPQttC1INCy0LLQtdC70Lgg0LzQvdC+0LbQtdGB0YLQstC+IDEiIDw8IGVuZGw7IHNldDEub3V0cHV0KCk7IH0KICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICBpZiAoY2hvb3NlID09ICcyJykKICAgICAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmIChwMiA9PSB0cnVlKXsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbWF4XzI7IGkrKykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY291dCA8PCAi0JLQstC10LTQuNGC0LUg0Y0t0YI6ICI7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNpbiA+PiB4OwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzZXQyLmFkZCh4KTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvdXQgPDwgItCf0L7Qu9GD0YfQuNCy0YjQtdC10YHRjyDQvNC90L7QttC10YHRgtCy0L4gMiIgPDwgZW5kbDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNldDIub3V0cHV0KCk7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICIgIiA8PCBlbmRsOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcDIgPSBmYWxzZTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZWxzZSB7IGNvdXQgPDwgItCS0Ysg0YPQttC1INCy0LLQtdC70Lgg0LzQvdC+0LbQtdGB0YLQstC+IDIiIDw8IGVuZGw7IHNldDIub3V0cHV0KCk7IH0KICAgICAgICAgICAgICAgICAgICAgICAgfQogCiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgY2FzZSAnNSc6c2V0MyA9IChzZXQxKnNldDIpOwogICAgICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICLQmNGB0YXQvtC00L3QvtC1INC80L3QvtC20LXRgdGC0LLQviAxIiA8PCBlbmRsOwogICAgICAgICAgICAgICAgICAgICAgICBzZXQxLm91dHB1dCgpOwogICAgICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICLQmNGB0YXQvtC00L3QvtC1INC80L3QvtC20LXRgdGC0LLQviAyIiA8PCBlbmRsOwogICAgICAgICAgICAgICAgICAgICAgICBzZXQyLm91dHB1dCgpOwogICAgICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICLQn9C+0LvRg9GH0LjQstGI0LXQtdGB0Y8g0LzQvdC+0LbQtdGB0YLQstC+IDMiIDw8IGVuZGw7CiAgICAgICAgICAgICAgICAgICAgICAgIHNldDMub3V0cHV0KCk7CiAgICAgICAgICAgICAgICAgICAgICAgIGNvdXQgPDwgIiAiIDw8IGVuZGw7CiAgICAgICAgICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgY2FzZSAnMCc6cmV0dXJuOwogICAgICAgICAgICAgICAgZGVmYXVsdDpjb3V0IDw8ICLQlNC10LnRgdGC0LLQuNC1INC90LUg0LLRi9Cx0YDQsNC90L4iOwogICAgICAgICAgICAgICAgfQogICAgICAgIH0gd2hpbGUgKHRydWUpOwogICAgICAKICAgICAgICAKfQp0ZW1wbGF0ZSA8Y2xhc3MgVD4KYm9vbCBzZXQgPFQ+OjpjaGVja19pbihUIHgpCnsKICAgICAgICBmb3IgKGludCBpID0gMDsgaTxzaXplOyBpKyspCiAgICAgICAgaWYgKGFbaV0gPT0geCkKICAgICAgICAgICAgICAgIHJldHVybiB0cnVlOwogICAgICAgIHJldHVybiBmYWxzZTsKfQp0ZW1wbGF0ZSA8Y2xhc3MgVD4Kdm9pZCBzZXQ8VD4gOjphZGQoVCB4KQp7CiAgICAgICAgaWYgKHNpemU8bWF4X3NpemUpCiAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKCFjaGVja19pbih4KSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgYVtzaXplXSA9IHg7CiAgICAgICAgICAgICAgICAgICAgICAgIHNpemUgKz0gMTsKICAgICAgICAgICAgICAgICAgICAgICAgY291dCA8PCAi0JTQvtCx0LDQstC70LXQvdC40LUg0L/RgNC+0YjQu9C+INGD0YHQv9C10YjQvdC+IiA8PCBlbmRsOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBjb3V0IDw8ICLQlNC+0LHQsNCy0LvQtdC90LjQtSDQvdC10LLQvtC30LzQvtC20L3QviEhISIgPDwgZW5kbDsKICAgICAgICAgICAgICAgICAgICAgICAgY291dCA8PCAi0J7QtNC40L3QsNC60L7QstGL0LUg0Y3Qu9C10LzQtdC90YLRiyDRgdC+0LTQtdGA0LbQsNGC0YzRgdGPINCyINC80L3QvtC20LXRgdGC0LLQtSDRgtC+0LvRjNC60L4g0L7QtNC40L0g0YDQsNC3ISEhIiA8PCBlbmRsOwogICAgICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICAgICAgY291dCA8PCAi0JTQvtCx0LDQstC70LXQvdC40LUg0L3QtdCy0L7Qt9C80L7QttC90L4iIDw8IGVuZGw7CiAgICAgICAgICAgICAgICBjb3V0IDw8ICLQoNCw0LfQvNC10YAg0LzQvdC+0LbQtdGB0YLQstCwINC90LUg0YHQvtC+0YLQstC10YLRgdGC0LLRg9C10YIg0LrQvtC70LjRh9C10YHRgtCy0YMg0Y3Qu9C10LzQtdC90YLQvtCyISEhIiA8PCBlbmRsOwogICAgICAgIH0KfQp0ZW1wbGF0ZSA8Y2xhc3MgVD4Kdm9pZCBzZXQ8VD46Om91dHB1dCgpCnsKICAgICAgICBpZiAoc2l6ZSA9PSAwKQogICAgICAgIHsKICAgICAgICAgICAgICAgIGNvdXQgPDwgInt9IjsKICAgICAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgY291dCA8PCAieyIgPDwgYVswXTsKICAgICAgICBmb3IgKGludCBpID0gMTsgaTxzaXplOyBpKyspCiAgICAgICAgICAgICAgICBjb3V0IDw8ICIsICIgPDwgYVtpXTsKICAgICAgICBjb3V0IDw8ICJ9IiA8PCBlbmRsOwogCn0KIAogCiAKIAogCnRlbXBsYXRlIDxjbGFzcyBUPgpzZXQ8VD4gc2V0PFQ+Ojogb3BlcmF0b3IqICggIHNldCA8VD4gJnMyKQp7CiAgICAgICAgaW50IGs7CiAgICAgICAgayA9IDA7CiAgICAgICAgc2V0IDxUPiBzKG1heF9zaXplKTsKICAgICAgICBzLnNpemUgPSAwOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrKQogICAgICAgICAgICAgICAgY291dCA8PCBhW2ldIDw8ICAiICI7CiAgICAgICAgY291dCA8PCBlbmRsOwogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgczIuc2l6ZTsgaisrKQogICAgICAgICAgICAgICAgY291dCA8PCAgczIuYVtqXSA8PCAiICI7CiAgICAgICAgY291dCA8PCBlbmRsOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2l6ZTsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgczIuc2l6ZTsgaisrKQogICAgICAgICAgICAgICAgaWYgKHMyLmFbal0gPT0gYVtpXSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICAgICAgICBzLmFba10gPSBzMi5hW2pdOwogICAgICAgICAgICAgICAgICAgICAgICBrKys7CiAgICAgICAgICAgICAgICAgICAgICAgIHMuc2l6ZSArPSAxOwogICAgICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAgCiAgICAgICAgcmV0dXJuIHM7Cn0KIAogCiAKIAogCnRlbXBsYXRlIDxjbGFzcyBUPgpzZXQ8VD4gc2V0PFQ+Ojogb3BlcmF0b3I9IChjb25zdCBzZXQgPFQ+ICZzKQp7CiAgICAgICAgaWYgKHRoaXMgPT0gJnMpCiAgICAgICAgICAgICAgICByZXR1cm4gKnRoaXM7CiAgICAgICAgaWYgKG1heF9zaXplICE9IHMubWF4X3NpemUpCiAgICAgICAgewogICAgICAgICAgICAgICAgZGVsZXRlW11hOwogICAgICAgICAgICAgICAgYSA9IG5ldyBUW3MubWF4X3NpemVdOwogICAgICAgICAgICAgICAgc2l6ZSA9IDA7CiAgICAgICAgICAgICAgICBtYXhfc2l6ZSA9IHMubWF4X3NpemU7CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGkgPSAwOyBpPG1heF9zaXplOyBpKyspCiAgICAgICAgewogICAgICAgICAgICAgICAgYVtpXSA9IHMuYVtpXTsKICAgICAgICB9CiAgICAgICAgc2l6ZSA9IHMuc2l6ZTsKICAgICAgICByZXR1cm4gKnRoaXM7Cn0KIAogCiAKIAogCiAKIAp0ZW1wbGF0ZSA8Y2xhc3MgVD4Kc2V0PFQ+OjpzZXQoaW50IG1heGltKQp7CiAgICAgICAgYSA9IG5ldyBUW21heGltXTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaTxtYXhpbTsgaSsrKQogICAgICAgICAgICAgICAgYVtpXSA9IDA7CiAgICAgICAgbWF4X3NpemUgPSBtYXhpbTsKICAgICAgICBzaXplID0gMDsKfQogCiAKdGVtcGxhdGUgPGNsYXNzIFQ+CnNldDxUPjo6c2V0KHNldDxUPiAmeCkKewogICAgICAgIG1heF9zaXplID0geC5tYXhfc2l6ZTsKICAgICAgICBhID0gbmV3IFRbbWF4X3NpemVdOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpPG1heF9zaXplOyBpKyspCiAgICAgICAgICAgICAgICBhW2ldID0geC5hW2ldOwp9CiAKIAp0ZW1wbGF0ZSA8Y2xhc3MgVD4Kc2V0PFQ+Ojp+c2V0KCkKewogICAgICAgIGRlbGV0ZVtdYTsKfQ==