#include <iostream>

#include <time.h>

using namespace std;

// ==== Динамические структуры данных

// ---- Stack

// LIFO (last in first out)

//

// push(T item)

// pop()

// peek()

// isEmpty()

// isFull();

// count();

// clear() erase()

//

//class Stack

//{

//private:

// int* _stack;

// int _count;

//public:

// Stack() : _stack{ nullptr }, _count{} {}

// void push(int item)

// {

// int* tmp;

// tmp = _stack;

//

// _stack = new int[_count + 1];

// ++_count;

//

// for (int i{}; i < _count - 1; i++)

// _stack[i] = tmp[i];

//

// _stack[_count - 1] = item;

//

// if (_count > 1)

// delete[] tmp;

//

// }

//

// int pop()

// {

// if (_count == 0)

// return -1;

//

// --_count;

//

// return _stack[_count];

// }

//

// int peek()

// {

// if (_count == 0)

// return -1;

//

// return _stack[_count - 1];

// }

//

// Stack(const Stack& obj)

// {

// _count = obj._count;

// _stack = new int[_count];

//

// for (int i = 0; i < _count; i++)

// _stack[i] = obj._stack[i];

// }

//

// Stack operator=(const Stack& obj)

// {

// if (this == &obj)

// return *this;

//

// if (_count > 0)

// {

// _count = 0;

// delete[] _stack;

// }

//

// _stack = new int[obj._count];

//

// _count = obj._count;

// for (int i = 0; i < _count; i++)

// _stack[i] = obj._stack[i];

//

// return *this;

// }

//

// ~Stack()

// {

// delete[] _stack;

// _stack = nullptr;

// }

//

// int count() { return _count; }

//

// bool isEmpty() { return _count == 0; }

//

// void print()

// {

// cout << "Stack: " << endl;

// if (_count == 0)

// cout << "is empty." << endl;

// else {

// for (int i = 0; i < _count; i++)

// {

// cout << "Item[" << i << "] = " << *(_stack + i) << endl;

// }

// }

//

// cout << endl;

// }

//};

//

//void main()

//{

// Stack st1;

// st1.print();

//

// st1.push(2);

// st1.push(12);

// st1.push(34);

// st1.push(4);

//

// st1.print();

//

// Stack st2;

// st2 = st1;

// st2.print();

//

// int t = st1.pop();

// cout << t << endl;

// st1.print();

// cout << st1.peek() << endl;

// st1.print();

//}

// ---- Queue

// FIFO (first in first out)

// ---- Простая очередь

//class Queue

//{

// int* _arr;

// int _capacity;

// int _count;

//public:

// Queue(int capacity);

// ~Queue();

// void add(int c);

// int extract();

// void clear();

// bool isEmpty();

// bool isFull();

// int getCount();

// void show();

//};

//

//Queue::Queue(int capacity)

//{

// _capacity = capacity;

// _arr = new int[_capacity];

// _count = 0;

//}

//Queue::~Queue()

//{

// delete[]_arr;

// _arr = nullptr;

//}

//void Queue::add(int c)

//{

// if (!isFull())

// _arr[_count++] = c;

//}

//int Queue::extract()

//{

// if (!isEmpty())

// {

// int temp = _arr[0];

// for (int i = 1; i < _count; i++)

// _arr[i - 1] = _arr[i];

// _count--;

//

// return temp;

// }

//

// return -1;

//}

//void Queue::clear()

//{

// _count = 0;

//}

//bool Queue::isEmpty()

//{

// return _count == 0;

//}

//bool Queue::isFull()

//{

// return _count == _capacity;

//}

//int Queue::getCount()

//{

// return _count;

//}

//void Queue::show()

//{

// cout << "\n-----------------------------------\n";

// for (int i = 0; i < _count; i++)

// {

// cout << _arr[i] << " ";

// }

// cout << "\n-----------------------------------\n";

//}

//

//void main()

//{

// srand(time(0));

// Queue q(25);

// for (int i = 0; i < 5; i++)

// {

// q.add(rand() % 50);

// }

// q.show();

// int a = q.extract();

// cout << a << endl;

// q.show();

//}

// ---- Кольцевая очередь

//class Queue

//{

// int* _arr;

// int _capacity;

// int _count;

//public:

// Queue(int capacity);

// ~Queue();

// void add(int c);

// int extract();

// void clear();

// bool isEmpty();

// bool isFull();

// int getCount();

// void show();

//};

//

//Queue::Queue(int capacity)

//{

// _capacity = capacity;

// _arr = new int[_capacity];

// _count = 0;

//}

//Queue::~Queue()

//{

// delete[]_arr;

// _arr = nullptr;

//}

//void Queue::add(int c)

//{

// if (!isFull())

// _arr[_count++] = c;

//}

//int Queue::extract()

//{

// if (!isEmpty())

// {

// int temp = _arr[0];

// for (int i = 1; i < _count; i++)

// _arr[i - 1] = _arr[i];

// /*_count--;*/

// _arr[_count - 1] = temp; // <-----------------------------

//

// return temp;

// }

//

// return -1;

//}

//void Queue::clear()

//{

// _count = 0;

//}

//bool Queue::isEmpty()

//{

// return _count == 0;

//}

//bool Queue::isFull()

//{

// return _count == _capacity;

//}

//int Queue::getCount()

//{

// return _count;

//}

//void Queue::show()

//{

// cout << "\n-----------------------------------\n";

// for (int i = 0; i < _count; i++)

// {

// cout << _arr[i] << " ";

// }

// cout << "\n-----------------------------------\n";

//}

//

//void main()

//{

// srand(time(0));

// Queue q(25);

// for (int i = 0; i < 5; i++)

// {

// q.add(rand() % 50);

// }

// q.show();

// int a = q.extract();

// cout << a << endl;

// q.show();

//}

// ---- Очередь с приориетным исключением

//class QueuePriority

//{

//private:

// int* _arr;

// int* _pri;

// int _capacity;

// int _count;

//public:

// QueuePriority(int capacity);

// ~QueuePriority();

// void push(int val, int priority);

// int pop();

// void clear();

// bool isEmpty();

// bool isFull();

// int getCount();

//

// friend std::ostream& operator<<(std::ostream& out, const QueuePriority& q);

//};

//

//QueuePriority::QueuePriority(int capacity)

//{

// _capacity = capacity;

// _arr = new int[_capacity];

// _pri = new int[_capacity];

// _count = 0;

//}

//QueuePriority::~QueuePriority()

//{

// delete[]_arr;

// delete[]_pri;

//}

//

//void QueuePriority::push(int val, int priority)

//{

// if (!isFull()) {

// _arr[_count] = val;

// _pri[_count] = priority;

// _count++;

// }

//}

//

//int QueuePriority::pop()

//{

// if (!isEmpty())

// {

// int maxPri = 0;

// int posMaxPri = 0;

//

// for (int i = 1; i < _count; i++)

// {

// if (maxPri < _pri[i])

// {

// maxPri = _pri[i];

// posMaxPri = i;

// }

// }

//

// int val = _arr[posMaxPri];

//

// for (int i = posMaxPri; i < _count - 1; i++) {

// _arr[i] = _arr[i + 1];

// _pri[i] = _pri[i + 1];

// }

//

// --_count;

//

// return val;

// }

//

// return -1;

//}

//

//void QueuePriority::clear()

//{

// _count = 0;

//}

//bool QueuePriority::isEmpty()

//{

// return _count == 0;

//}

//bool QueuePriority::isFull()

//{

// return _count == _capacity;

//}

//int QueuePriority::getCount()

//{

// return _count;

//}

//

//std::ostream& operator<<(std::ostream& out, const QueuePriority& q)

//{

// for (int i = 0; i < q._count; i++)

// {

// out << q._arr[i] << " - " << q._pri[i] << "\n";

// }

// out << "\n-----------------------------------\n";

//

// return out;

//}

//

//void main()

//{

// QueuePriority q(25);

// q.push(12, 0);

// q.push(13, 0);

// q.push(45, 1);

// q.push(23, 1);

// q.push(56, 0);

// q.push(78, 0);

// q.push(45, 0);

// q.push(36, 1);

//

// cout << q;

//

// q.pop();

// cout << q;

//

// q.pop();

// cout << q;

//

// q.pop();

// cout << q;

//

// q.pop();

// cout << q;

//}