Alghoritms

#include<iostream>
#include<cmath>
#include<stdio.h>
using namespace std;

#define MAX(a,b) ((a>b) ? a : b)
#define MIN(a,b) ((a>b) ? b : a)

template<typename T>
inline unsigned secvention_search(T *v, unsigned n,T x)
{
	unsigned i;
	for (i = 0; i < n;i++)
	if (v[i] == x)
		return i;
	return 0;
}

template<typename T>
inline unsigned binary_search(T *v, unsigned le, unsigned ri, T x)   //vector,primul indice,ultimul indice+1,numarul de cautat
{
	if (x > v[ri - 1])
		return 0;
	else
	{
		if (le == ri)
		{
			if (v[le] == x)
				return le + 1;			//+1 deoarece se pleaca cu indici de la 0
			else
				return 0;
		}
		else
		{
			int m = (le + ri) / 2;
			if (v[m] == x)
				return m + 1;				//+1 deoarece se pleaca cu indici de la 0
			else if (v[m] < x)
				return binary_search(v, m, ri, x);
			else
				return binary_search(v, le, m, x);
		}
	}
}

template<typename T>
inline unsigned binary_search_iterative(T *v, unsigned le, unsigned ri, T x)
{
	unsigned m,ok;
	m = (le + ri) / 2;
	ok = 1;
	if (x > v[ri] || x < v[le])
		return 0;
	else
	{
		while (le < ri)
		{
			m = (le + ri) / 2;
			if (v[m] == x)
			{
				return m;
				ok = 0;
			}
			else
			{
				if (x > v[m])
					le = m;
				else
					ri = m;
			}
		}
	}

	if (ok)
		return 0; //nu a gasit
}

template <typename T>
inline bool prim(T x)
{
	if (x == 2)return true;
	else if (x == 1)return false;
	else 
	for (int i = 2; i <= sqrt(x);i++)
		if (x % i == 0)return false;
	
	return true;
}

inline void ciur_eratostene(int *v, int n)
{
	int i;
	v[1] = 0;
	for (i = 2; i <= n;i++)
		if (v[i])
		for (int j = i*i; j <= n; j += i)
			v[j] = 0;
}

template <typename T>
inline void swap_(T &a, T &b)
{
	T c = a;
	a = b;
	b = c;
}

template <typename T>
inline void buble_sort(T *v, T n)
{
	for (int i = 0; i < n;i++)
	for (int j = i + 1; j < n;j++)
	if (v[i]>v[j])
	{
		int aux = v[i];
		v[i] = v[j];
		v[j] = aux;
	}
}


template <typename T>
inline unsigned descomp_number(T *v, T n)
{
	int r,nr = 0;
	while (n)
	{
		r = n % 10;
		v[nr] = r;
		n /= 10;
		nr++;
	}
	return nr;
}


template<typename T>
class Stack
{
private:
	struct nod
	{
		T val;
		nod *next;
	};
	typedef nod _stack;
	_stack *first;
public:
	Stack();
	~Stack();
	void addStack(T v);      //adauga in stiva
	void popStack();           //sterge varful stivei
	void printStack();
	bool find_Stack(T x);
	void sort_Stack(int n);
	unsigned number_elements_Stack();
};

template<typename T> Stack<T>::Stack(){}

template<typename T> Stack<T>::~Stack()
{
	delete(first);
}

template<typename T> void Stack<T>::addStack(T v)
{
	_stack *p;
	p = new _stack;
	p->val = v;
	p->next = first;
	first = p;
}

template<typename T> void Stack<T>::popStack()
{
	_stack *p;
	p = first->next;
	delete(first);
	first = p;
}

template<typename T> void Stack<T>::printStack()
{
	_stack *p;
	p = first;
	while (p != NULL)
	{
		cout << p->val << " ";
		p = p->next;
	}
}

template<typename T> bool Stack<T>::find_Stack(T x)
{
	_stack *p;
	p = first;
	while (p->next!=NULL && p->val != x)
		p = p->next;

	if (p->val == x)
		return true;
	else
		return false;
}

template<typename T> unsigned Stack<T>::number_elements_Stack()
{
	_stack *p;
	int nr = 0;
	p = first;
	while (p)
	{
		nr++;
		p = p->next;
	}
	return nr;
}

template<typename T> void Stack<T>::sort_Stack(int n)
{
	_stack *p;
	int aux;
	p = first;
	for (int i = 1; i < n;i++)
	{
		if (p->val > p->next->val)
		{
			aux = p->val;
			p->val = p->next->val;
			p->next->val = aux;
		}
		p = p->next;
	}
}

template<typename T>
inline void insert_sort(T *v, T n)
{
	T x;
	int i, j;	
	for (i = 1; i < n; i++)
	{
		x = v[i];
		j = i - 1;
		while ((j >= 0) && (x < v[j]))
		{
			v[j + 1] = v[j];
			j--;
		}
		v[j + 1] = x;
	}
}

template<typename T>
inline void insert_sort_min(T *v, T n)
{
	int i, j, k;
	T min;
	for (i = 0; i < n - 1; i++)
	{
		min = v[i];
		k = i;
		for (j = i + 1; j < n;j++)
		if (min > v[j])
		{
			min = v[j];
			k = j;
		}
		v[k] = v[i];
		v[i] = min;
	}
}

template<typename T>
inline void cicle_vector(T *v, T n)
{
	T aux;
	int i;
	aux = v[0];
	for (i = 1; i < n; i++)
		v[i - 1] = v[i];
	v[n - 1] = aux;
}

template<typename T>
inline void inversion_vector(T *v, T n)
{
	int i, j;
	T aux;
	i = 0;
	j = n - 1;
	while (i < j)
	{
		aux = v[i];
		v[i] = v[j];
		v[j] = aux;
		i++;
		j--;
	}
}

template<typename T>
inline void interchange_sort(T *v, T n)
{
	int i, j, ok;
	T aux;
	ok = 1;
	for (i = 2; i <= n && ok == 1; i++)
	{
		ok = 0;
		for (j = n - 1; j > 0;j--)
		if (v[j] < v[j - 1])
		{
			aux = v[j];
			v[j] = v[j - 1];
			v[j - 1] = aux;
			ok = 1;
		}
	}
}

template<typename T>
inline void shell_sort(T *v, T n)
{
	int d, i, j,flag;
	T aux;
	flag = 1;
	d = n;
	while ((d > 1) || (flag))
	{
		flag = 0;
		d = (d + 1) / 2;
		for (i = 0;  i < n - d; i++)
		{
			if (v[i + d] < v[i])
			{
				aux = v[i + d];
				v[i + d] = v[i];
				v[i] = aux;
				flag = 1;
			}
		}
	}
}

template<typename T>
class Queue
{
private: 
	struct nod
	{
		T val;
		nod *next;
	};
	typedef nod _queue;
	_queue *first, *last;
	unsigned count;
public:
	Queue();
	~Queue();
	void addQueue(T v);
	void popQueue();
	unsigned nr_elements_Queue();
	bool find_Queue(T v);
	void printQueue();
};

template<typename T>Queue<T>::Queue()
{
	count = 0;
}

template<typename T>Queue<T>::~Queue()
{
	delete(first);
}

template<typename T>void Queue<T>::addQueue(T v)
{
	_queue *p;
	p = new _queue;
	if (count == 0)
	{
		first = new _queue;
		first->val = v;
		first->next = NULL;
		last = first;
		count++;
	}
	else
	{
		p->val = v;
		p->next = NULL;
		last->next = p;
		last = p;
		count++;
	}
}

template<typename T>void Queue<T>::printQueue()
{
	_queue *p;
	p = first;
	while (p)
	{
		cout << p->val << " ";
		p = p->next;
	}
}

template<typename T>void Queue<T>::popQueue()
{
	_queue  *p;
	p = first;
	cout << p->val << " ";
	p = p->next;
	first = p;
}

template<typename T>unsigned Queue<T>::nr_elements_Queue()
{
	return count;
}

template<typename T>bool Queue<T>::find_Queue(T x)
{
	_queue *p;
	p = first;
	while (p)
	{
		if (p->val == x)
			return true;
		p = p->next;
	}
	return false;
}

template<typename T>
class List
{
private:
	struct nod
	{
		T val;
		nod *next;
	};
	typedef nod list;
	list *first, *last; 
	unsigned count;
public:
	List();
	~List();
	void add_front_list(T x);
	void add_back_list(T x);
	void print_list();
	unsigned number_elements();
	void pop_front_list();
	void pop_back_list();
};

template<typename T>List<T>::List()
{
	count = 0;
}

template<typename T>List<T>::~List()
{
	delete(first);
}

template<typename T>void List<T>::print_list()
{
	list *p;
	p = first;
	while (p)
	{
		cout << p->val << " ";
		p = p->next;
	}
}

template<typename T>void List<T>::add_front_list(T x)
{
	list *p;
	if (count == 0)
	{
		first = new list;
		first->val = x;
		first->next = NULL;
		last = first;
		count++;
	}
	else
	{
		p = new list;
		p->val = x;
		p->next = NULL;
		last->next = p;
		last = p;
		count++;
	}
}

template<typename T>void List<T>::add_back_list(T x)
{
	list *p;
	p = new list;
	p->val = x;
	p->next = first;
	first = p;
	count++;
}

template<typename T>void List<T>::pop_back_list()
{
	list *p;
	p = first;
	int i = 0;
	while (i < count-2)
	{
		p = p->next;
		i++;
	}
	list *p2 = p->next;
	p->next = NULL;
	delete(p2);
	count--;
}

template<typename T>void List<T>::pop_front_list()
{
	list *p = first;
	first = first->next;
	delete(p);
	count--;
}

template<typename T>unsigned List<T>::number_elements()
{
	return count;
}

class Rational
{
private:
	int _n;
	int _d;
public:
	Rational(int numerator = 0, int denominator = 1) :_n(numerator), _d(denominator){};
	Rational(const Rational &rhs) :_n(rhs._n), _d(rhs._d){};
	~Rational();
	inline int numerator()const{ return _n; };
	inline int denominator()const{ return _d; };
	int divizor();
	void reduction();
	Rational & operator = (const Rational&);
	Rational operator +(const Rational&)const;
	Rational operator -(const Rational&)const;
	Rational operator *(const Rational&)const;
	Rational operator /(const Rational&)const;
};
Rational &Rational::operator=(const Rational &rhs)
{
	if (this != &rhs)
	{
		_n = rhs.numerator();
		_d = rhs.denominator();
	}
	return *this;
}
Rational Rational::operator+(const Rational &rhs)const
{
	return Rational((_n*rhs._d) + (_d*rhs._n), _d*rhs._d);
}
Rational Rational::operator-(const Rational&rhs)const
{
	return Rational((_n * rhs._d) - (_d*rhs._n), _d*rhs._d);
}
Rational Rational::operator*(const Rational&rhs)const
{
	return Rational(_n*rhs._n, _d*rhs._d);
}
Rational Rational::operator/(const Rational&rhs)const
{
	return Rational(_n*rhs._d, _d*rhs._n);
}
Rational::~Rational()
{
	cout << _n << "/" << _d << endl;
	_n = 0;
	_d = 1;
}
std::ostream &operator<<(std::ostream &o, const Rational &r)
{
	return o << r.numerator() << "/" << r.denominator();
}
int Rational::divizor()
{
	int r, _d1, _n1;
	_d1 = _d;
	_n1 = _n;
	while (_d1)
	{
		r = _n1 % _d1;
		_n1 = _d1;
		_d1 = r;
	}
	return _n1;
}
void Rational::reduction()
{
	int _n1, _d1, d;
	_n1 = _n;
	_d1 = _d;
	d = divizor();
	if ((_n1 > _d1) && (d != 0))
	{
		while ((_n1 > _d1) && (d != 0) && (_d1>0))
		{
			_n1 /= d;
			_d1 /= d;
			if (_n1%_d1 != 0)
				break;
		}
	}
	_d = _d1;
	_n = _n1;
}

class Complex
{
private:
	int _re;
	int _im;
public:
	struct _rational
	{
		int _r;
		int _i;
		int _d;
	};
	Complex(int real = 0, int imaginar = 0) :_re(real), _im(imaginar){};
	Complex(const Complex &rhs) :_re(rhs._re), _im(rhs._im){};
	~Complex();
	inline int real()const { return _re; };
	inline int imaginar()const{ return _im; };
	int conjugate();
	Complex operator+(const Complex&)const;
	Complex operator-(const Complex&)const;
	Complex operator*(const Complex&)const;
	_rational operator/(const Complex&);
	Complex& operator=(const Complex&);
};
Complex::_rational Complex::operator/(const Complex& rhs)
{
	_rational a;
	a._r = (_re*rhs._re) + (_im*rhs._im);
	a._i = ((_im*rhs._re) - (_re*rhs._im));
	a._d = (rhs._re*rhs._re) - (rhs._im*rhs._im);
	return a;
}
Complex Complex::operator+(const Complex &rhs)const
{
	return Complex(_re + rhs._re, _im + rhs._im);
}
Complex Complex::operator-(const Complex &rhs)const
{
	return Complex(_re - rhs._re, _im - rhs._im);
}
Complex Complex::operator*(const Complex &rhs)const
{
	return Complex((_re*rhs._re) - (_im*rhs._im), (_re*rhs._im) + (_im*rhs._re));
}
Complex &Complex::operator=(const Complex &rhs)
{
	if ((this != &rhs))
	{
		_im = rhs._im;
		_re = rhs._re;
	}
	return *this;
}
int Complex::conjugate()
{
	return ((_re*_re) - (_im*_im));
}
Complex::~Complex()
{
	cout << "Real = " << _re << "  and Imaginar = " << _im << endl;
	_re = 0;
	_im = 0;
}
std::ostream &operator<<(ostream &o, Complex &a)
{
	return o << "Real = " << a.real() << "  and Imaginar = " << a.imaginar() << endl;
}
std::ostream &operator<<(ostream &o, Complex::_rational &a)
{
	return o << "(Real = " << a._r << "  and Imaginar = " << a._i << ") / " << a._d << endl;
}

template<typename T>
class Stack_static
{
private:
	T *stack;
	int top;
public:
	Stack_static(unsigned number);
	~Stack_static();
	void push_Stack(T x);
	void pop_Stack();
	bool empty_Stack();
	unsigned number_elements();
	void sort_Stack();
};
template<typename T>Stack_static<T>::Stack_static(unsigned number)
{
	top = 0;
	stack = new T[number+1];
}
template<typename T>Stack_static<T>::~Stack_static()
{
	top = 0;
	delete(stack);
}
template<typename T>void Stack_static<T>::push_Stack(T x)
{
	if (top == 0)
	{
		stack[top] = x;
		top++;
	}
	else
	{
		stack[top] = x;
		top++;
	}
}
template<typename T>void Stack_static<T>::pop_Stack()
{
	if (top == 0)
		cout << "Stack is empty! " << endl;
	else
	{
		--top;
		cout << stack[top] <<" ";
	}
}
template<typename T>bool Stack_static<T>::empty_Stack()
{
	if (top == 0)
		return true;
	else
		return false;
}
template<typename T>unsigned Stack_static<T>::number_elements()
{
	return top;
}
template<typename T>void Stack_static<T>::sort_Stack()
{
	
	for (int i = 0; i <= top;i++)
	for (int j = i + 1; j < top; j++)
	if (stack[i] < stack[j])
	{
		T aux = stack[i];
		stack[i] = stack[j];
		stack[j] = aux;
	}
}

template<typename T>
class Queue_static
{
private:
	int tail;
	int top;
	T *queue;
public:
	Queue_static(int);
	~Queue_static();
	void push_queue(T);
	void pop_queue();
	bool empty_queue();
	unsigned number_elements();
	void sort_queue();
};
template<typename T>Queue_static<T>::Queue_static(int nr)
{
	queue = new T[nr + 1];
	tail = top = 0;
}
template<typename T>Queue_static<T>::~Queue_static()
{
	delete(queue);
}
template<typename T>void Queue_static<T>::push_queue(T x)
{
	if (top == 0)
	{
		queue[top] = x;
		top++;
	}
	else
	{
		queue[top] = x;
		top++;
	}
}
template<typename T>void Queue_static<T>::pop_queue()
{
	if (top == tail)
		cout << "Queue is vide!" << endl;
	else
	{
		cout << queue[tail] << " ";
		tail++;
	}
}
template<typename T>bool Queue_static<T>::empty_queue()
{
	if (top == tail)
		return true;
	else
		return false;
}
template<typename T>unsigned Queue_static<T>::number_elements()
{
	return (top - tail);
}
template<typename T>void Queue_static<T>::sort_queue()
{
	for (int i = 0; i < top; i++)
	for (int j = i + 1; j < top;j++)
	if (queue[i]>queue[j])
	{
		T aux = queue[i];
		queue[i] = queue[j];
		queue[j] = aux;
	}
}

int Euler(int a, int b)
{
	while (b)
	{
		int c = a%b;
		a = b;
		b = c;
	}
	return a;
}

class Game_move
{
private:
	enum d{ UP, DOWN, RIGHT, LEFT, STOP = 0 };
	d dir = STOP;
	int x = 10, y = 10;
	bool gameover = false;
	char k;
public:
	Game_move()
	{
		while (!gameover)
		{

			print();
			input();
			logic();
		}
	}
	void print()
	{
		for (int i = 0; i <= 20; i++)
		{
			for (int j = 0; j <= 20; j++)
			if (i == y && j == x)
				cout << "0";
			else
				cout << " ";
			cout << endl;
		}
	}
	void logic()
	{
		switch (dir)
		{
		case LEFT:
			x--;
			break;
		case RIGHT:
			x++;
			break;
		case UP:
			y--;
			break;
		case DOWN:
			y++;
			break;
		default:
			break;
		}
	}
	void input()
	{
		switch (_getch())
		{
		case'a':
			dir = LEFT;
			break;
		case 'd':
			dir = RIGHT;
			break;
		case'w':
			dir = UP;
			break;
		case's':
			dir = DOWN;
			break;
		case'x':
			gameover = true;
		default:
			break;
		}
	}
};

class Graph
{
private:
#define NMax 100
	int graph[NMax][NMax],p[NMax],g[NMax],t[NMax],queue[NMax]; // p-vector de vizitat  || g-vector pentru gradul fiecarui node
	int x, y, n, edges, root;                 //t-vector tati , queue-coada pentru BF 
public:
	Graph(int nodes);
	~Graph();
	void init_graph(int e);
	void init_graph_list(int e);
	int grade_node(int x);
	void all_grade_nodes();
	void DF(int s);
	void BF(int s);
	bool is_conex();
	bool is_Eulerian();
	void ciclu_Eulerian(int k);
	void group_edges_incidents();
	void algorithm_Roy_Floyd();
	void chain(int k);
	inline void set_root(int r){ root = r; };
	inline int get_root(){ return root; };
};
Graph::Graph(int nodes) :n(nodes)
{
	for (int i = 1; i <= n;i++)
	for (int j = 1; j <= n; j++)
		graph[i][j] = 0;
	for (int i = 1; i <= n; i++)
		p[i] = 0;
}
Graph::~Graph()
{
	int i, j;
	for (i = 0; i <= n;i++)
	for (j = 0; j <= n; j++)
		graph[i][j] = 0;
	n = 0;
	edges = 0;
}
void Graph::init_graph(int e)
{
	int i;
	for (i = 1; i <= e; i++)
	{
		cin >> x >> y;
		graph[x][y] = 1;
		graph[y][x] = 1;
	}
}
void Graph::init_graph_list(int e)
{
	int i;
	for (i = 1; i <= e; i++)
	{
		cin >> x >> y;
		graph[x][0]++; graph[x][graph[x][0]] = y;
		graph[y][0]++; graph[y][graph[y][0]] = x;
	}
}
int Graph::grade_node(int x)
{
	int nr = 0;
	for (int i = 1; i <= n; i++)
		if (graph[x][i]== 1)
			nr++;
	return nr;
}
void Graph::DF(int k)
{
	p[k] = 1;
	for (int i = 1; i <= n;i++)
	if (graph[k][i] == 1 && p[i] == 0)
		DF(i);
}
bool Graph::is_conex()
{
	DF(1);
	for (int i = 1; i <= n;i++)
	if (p[i] == 0)return false;
	return true;
}
bool Graph::is_Eulerian()
{
	if (!is_conex())
		return false;
	for (int i = 1; i <= n;i++)
	if (g[i] % 2 == 1)
		return false;
	return true;
}
void Graph::all_grade_nodes()
{
	for (int i = 1; i <= n; i++)
		g[i] = grade_node(i);
}
void Graph::ciclu_Eulerian(int k)
{
	int i, maxx, nmax;
	maxx = nmax = 0;
	cout << k << " ";
	for (i = 1; i <= n; i++)
	{
		if (graph[k][i]==1)
		if (g[i] > maxx)
		{
			maxx = grade_node(i);
			nmax = i;
		}
	}
	if (nmax != 0)
	{
		graph[k][nmax] = graph[nmax][k] = 0;
		g[k]--;
		g[nmax]--;
		ciclu_Eulerian(nmax);
	}
}
void Graph::group_edges_incidents()
{
	all_grade_nodes();
	for (int i = 1; i <= n;i++)
	if (g[i] >= 2)
	{
		for (int j = 1; j <= n;j++)
		if (graph[i][j] == 1)
			cout << "[" << i << "," << j << "] ";
		cout << endl;
	}
}
void Graph::algorithm_Roy_Floyd()
{
	int i, j, k;
	for (k = 1; k <= n;k++)
	for (i = 1; i <= n;i++)
	for (j = 1; j <= n;j++)
	if (i!=j)
	if (graph[i][j] > (graph[i][k] + graph[k][j]))
		graph[i][j] = graph[i][k] + graph[k][j];
}
//mai trebuie lucrat aici
void Graph::BF(int k)
{
	int st, dr, j;
	st = dr = 1;
	queue[1] = k;
	p[k] = 1;
	while (st <= dr)
	{
		for (j = 1; j <= n;j++)
		if (graph[queue[st]][j] == 1 && p[j] == 0)
		{
			dr++;
			queue[dr] = j;
			p[j] = 1;
			t[j] = queue[st];
		}
		st++;
	}
}
//mai trebuie lucrat aici
void Graph::chain(int k)
{
	if (t[k] != 0)
		chain(t[k]);
	cout << k << " ";
}

class Tree_binary_for_search
{
private:
	struct tree
	{
		int key_value;
		tree *right, *left;
	};
	tree *Root;
	void delete_tree(tree*leaf);
	void insert(int key, tree *leaf);
	tree*search(int key, tree*leaf);
public:
	Tree_binary_for_search();
	~Tree_binary_for_search();
	void insert(int key);
	tree *search(int key);
	void delete_tree();
	inline tree* set_root(){ return Root; };
	tree* print_tree(tree*root);
};

Tree_binary_for_search::Tree_binary_for_search()
{
	Root = NULL;
}
Tree_binary_for_search::~Tree_binary_for_search()
{
	delete_tree();
}
void Tree_binary_for_search::delete_tree(tree*leaf)
{
	if (leaf != NULL)
	{
		delete_tree(leaf->left);
		delete_tree(leaf->right);
		delete leaf;
	}
}
void Tree_binary_for_search::insert(int key,tree*leaf)
{
	if (key < leaf->key_value)
	{
		if (leaf->left != NULL)
			insert(key, leaf->left);
		else
		{
			leaf->left = new tree;
			leaf->left->key_value = key;
			leaf->left->left = NULL;
			leaf->left->right = NULL;
		}
	}
	else if (key>=leaf->key_value)
	{
		if (leaf->right != NULL)
			insert(key, leaf->right);
		else
		{
			leaf->right = new tree;
			leaf->right->key_value = key;
			leaf->right->left = NULL;
			leaf->right->right = NULL;
		}
	}
}
Tree_binary_for_search::tree* Tree_binary_for_search::search(int key, tree*leaf)
{
	if (leaf != NULL)
	{
		if (key == leaf->key_value)
			return leaf;
		if (key < leaf->key_value)
			return search(key, leaf->left);
		else
			return search(key, leaf->right);
	}
	else
		return NULL;
}
void Tree_binary_for_search::insert(int key)
{
	if (Root != NULL)
		insert(key, Root);
	else
	{
		Root = new tree;
		Root->key_value = key;
		Root->left = NULL;
		Root->right = NULL;
	}
}
Tree_binary_for_search::tree *Tree_binary_for_search::search(int key)
{
	return search(key, Root);
}
void Tree_binary_for_search::delete_tree()
{
	delete_tree(Root);
}
Tree_binary_for_search::tree* Tree_binary_for_search::print_tree(tree *root)
{
	tree *p;
	p = root;
	while (p != NULL)
	{
		cout << p->key_value << " ";
		if (p->left != NULL)
			return print_tree(p->left);
		else if (p->right != NULL)
			return print_tree(p->right);
		else return 0;
	}
	return 0;
}
//mai treb lucrat la delete

template<int MOD>
class Zn
{
private:
	long long value;
public:
	Zn(int value = 0)
	{
		this->value = ((value%MOD) + MOD) % MOD;
	}
	Zn operator*(const Zn&other)const
	{
		return (this->value*other.value) % MOD;
	}
	Zn operator+(const Zn&other)const
	{
		return(this->value + other.value) % MOD;
	}
	Zn operator-()const
	{
		return (MOD - this->value) % MOD;
	}
	Zn operator-(const Zn&other)const
	{
		return (this->value - other.value + MOD) % MOD;
	}
	Zn operator^(const unsigned int exp)const
	{
		if (exp == 0)
			return Zn(1);
		else if (exp % 2 == 1)
			return (*this)*((*this) ^ (exp - 1));
		else
		{
			Zn ab2 = (*this) ^ (exp / 2);
			return ab2*ab2;
		}
	}
	Zn operator/(const Zn&other)const
	{
		return (*this)*(other ^ (unsigned int)(MOD - 2));
	}
	operator int()const
	{
		return long(this->value);
	}
	Zn& operator=(const Zn&other)
	{
		if (this != &other)
		{
			this->value = other.value;
		}
		return *this;
	}
	int get_value(){ return long(value); };
	friend ostream &operator<<(ostream &o, Zn &a)
	{
		o << a.get_value();
		return o;
	}
};

ifstream fin("test.in");
class Huge
{
private:
	long long *a, *b, *c;
	int n1, n2,n3;
public:
	Huge(unsigned ,unsigned );
	void read();
	void result();
	void add();
	void decrease();
	void AtribValue(int *H, unsigned long X); //atribuire inmultire
	void inmultire_huge(int *A, int *B, int *C); //vectorul 3 este rezultatul inmutiri vector a cu b
};
void Huge::inmultire_huge(int *A, int *B, int *C)
{
	int i, j, T = 0;

	C[0] = A[0] + B[0] - 1;
	for (i = 1; i <= A[0] + B[0];)
		C[i++] = 0;
	for (i = 1; i <= A[0]; i++)
	for (j = 1; j <= B[0]; j++)
		C[i + j - 1] += A[i] * B[j];

	for (i = 1; i <= C[0]; i++)
	{
		T = (C[i] += T) / 10;
		C[i] %= 10;
	}

	if (T)
		C[++C[0]] = T;
}
void Huge::AtribValue(int *H, unsigned long X) 
{
	H[0] = 0;
	while (X) {
		++H[0];
		H[H[0]] = X % 10;
		X /= 10;
	}
}
Huge::Huge(unsigned nr1, unsigned nr2) :n1(nr1), n2(nr2)
{
	a = new long long[n1*2];
	b = new long long[n2*2];
	for (int i = 0; i <= n1; i++)
		a[i] = 0;
	for (int i = 0; i <= n2; i++)
		b[i] = 0;
	if (n1 > n2)
		n3 = n1;
	else
		n3 = n2;
	c = new long long[n3*5];
	for (int i = 0; i <= n3; i++)
		c[i] = 0;
}
void Huge::read()
{
	cout << "First number:  ";
	int contor;
	char nr;
	contor = 1;
	while (!fin.eof() && (contor <= n1))
	{
		fin >> nr;
		a[contor] = nr - '0';
		contor++;
	}
	contor = 1;
	
	while (!fin.eof() && (contor <= n2))
	{
		fin >> nr;
		b[contor] = nr - '0';
		contor++;
	}
	for (int i = 1; i <= n1; i++)
		cout << a[i];
	cout << endl;
	cout << "Second number: ";
	for (int i = 1; i <= n2; i++)
		cout << b[i];
	cout << endl;

}
void Huge::add()
{
	int cpy_n;
	if (n1 == n2)
	{
		for (int i = n1; i >= 1; i--)
		{
			if ((a[i] + b[i]) > 9)
			{
				c[i] = (a[i] + b[i]) % 10;
				a[i - 1]++;
			}
			else
				c[i] = a[i] + b[i];
			if (a[0] != 0)
				c[0] = a[0];
		}
	}
	else if (n1 > n2)
	{
		cpy_n = n2;
		for (int i = n1; i >= 1; i--)
		{
			if ((n2 - i-1) <= 0)                     
			{                                       
				if ((a[i] + b[cpy_n]) > 9)
				{
					c[i] = (a[i] + b[cpy_n]) % 10;
					a[i - 1]++;
				}
				else
					c[i] = a[i] + b[cpy_n];
				cpy_n--;
			}
			else
				c[i] = a[i];

			if (a[0] != 0)
				c[0] = a[0];
		}
	}
	else
	{
		cpy_n = n1;
		for (int i = n2; i >= 1; i--)
		{
			if ((n1 - i-1) <= 0)
			{
				if ((a[cpy_n] + b[i]) > 9)
				{
					c[i] = (a[cpy_n] + b[i]) % 10;
					b[i - 1]++;
				}
				else
					c[i] = a[cpy_n] + b[i];
				cpy_n--;
			}
			else
				c[i] = b[i];
			if (b[0] != 0)
				c[0] = b[0];
		}
	}
}

void Huge::result()
{
	cout << "Result = ";
	int ok = 0,d;
	d = 0;
	while (!ok)
	{
		if (c[d] == 0)
			d++;
		else
			ok = 1;
	}

	if (c[0] == 0)
	{
		for (int i = d; i <= n3; i++)
			cout << c[i];
		cout << endl;
	}
	else
	{
		for (int i = d; i <= n3; i++)
			cout << c[i];
		cout << endl;
	}
}

void Huge::decrease()
{
	int cpy_n;
	if (n1 == n2)
	{
		if (a[1] > b[1])
		{
			for (int i = n1; i >= 1; i--)
			{
				if ((a[i] - b[i]) < 0)
				{
					c[i] = a[i] + 10 - b[i];
					a[i - 1]--;
				}
				else
					c[i] = a[i] - b[i];
			}
		}
		else
		{
			for (int i = n1; i >= 1; i--)
			{
				if ((b[i] - a[i]) < 0)
				{
					c[i] = b[i] + 10 - a[i];
					b[i - 1]--;
				}
				else
					c[i] = b[i] - a[i];
			}
		}
	}
	else if (n1>n2)
	{
		cpy_n = n2;
		for (int i = n1; i >= 1; i--)
		{
			if ((n2 - i - 1) <= 0)
			{
				if ((a[i] - b[cpy_n]) < 0)
				{
					c[i] = (a[i] + 10) - b[cpy_n];
					a[i - 1]--;
				}
				else
					c[i] = a[i] - b[cpy_n];
				cpy_n--;
			}
			else
				c[i] = a[i];
		}
	}
	else
	{
		cpy_n = n1;
		for (int i = n2; i >= 1; i--)
		{
			if ((n1 - i-1) <= 0)
			{
				if ((b[i] - a[cpy_n]) < 0)
				{
					c[i] = b[i] + 10 - a[cpy_n];
					b[i - 1]--;
				}
				else
					c[i] = b[i] - a[cpy_n];
				cpy_n--;
			}
			else
				c[i] = b[i];
		}
	}
}

template<typename T>
T pivot(T *a, int p, int q)
{
	T x, t;
	x = a[(p + q) / 2];
	while (p < q)
	{
		while (a[q] > x)q--;
		while (a[p] < x)p++;
		if (p < q)
		{
			t = a[p];
			a[p] = a[q];
			a[q] = t;
		}
	}
	return p;
}

template<typename T>
void qsort(T *a, int i, int j)
{
	T m;
	if (i < j)
	{
		m = pivot(a, i, j);
		qsort(a, i, m);
		qsort(a, m + 1, j);
	}
}

template<typename T>
class Double_list
{
private:
	struct nod
	{
		T info;
		nod*next, *prev;
	};
	typedef nod List;
	List *head,*last;
	int count;
public:
	Double_list();
	~Double_list();
	void push(T x);
	void pop(int n);
	inline int get_count(){ return count; };
	void print_front();
	void print_back();
	void sort();
};

template<typename T>Double_list<T>::Double_list()
{
	count = 0;
}
template<typename T>void Double_list<T>::push(T x)
{
	if (head == NULL)
	{
		head = new List;
		head->info = x;
		head->next = NULL;
		head->prev = NULL;
		last = head;
	}
	else
	{
		List *p = new List;
		p->info = x;
		p->next = NULL;
		p->prev = head;
		head->next = p;
		head = p;
	}
	count++;
}
template<typename T>void Double_list<T>::pop(int n)
{
	List *p = last;
	int i = 1;
	if (n == 1)
	{
		p->next->prev = NULL;
		last = p->next;
		delete(p);
	}
	else if (n == count)
	{
		head->prev->next = NULL;
		p = head;
		head = head->prev;
		delete(p);
	}
	else
	{
		while (i <= n - 2)
		{
			p = p->next;
			i++;
		}
		List *p2 = p->next;
		p = p->next;
		p->prev->next = p->next;
		p->next->prev = p->prev;
		delete(p2);
		count--;
	}
}
template<typename T>void Double_list<T>::print_front()
{
	List *p = last;
	while (p)
	{
		cout << p->info << " ";
		p = p->next;
	}
}
template<typename T>void Double_list<T>::print_back()
{
	List *p;
	p = head;
	while (p)
	{
		cout << p->info << " ";
		p = p->prev;
	}
}
template<typename T>Double_list<T>::~Double_list()
{
	delete(head);
	delete(last);
}
template<typename T>void Double_list<T>::sort()
{
	List*p,*p2;
	p = last;
	p2 = last;
	for (int i = 1; i < count; i++)
	{
		p = p2;
		for (int j = i+1; j < count+1; j++)
		{
			if (p2->info > p->next->info)
			{
				T aux = p2->info;
				p2->info = p->next->info;
				p->next->info = aux;
			}
			p = p->next;
		}
		p2 = p2->next;
	}
	
}

template<typename T>
void swap_math(T &a, T &b)
{
	a = a + b;
	b = a - b;
	a = a - b;

	/*
	a = a-b;
	b = a+b;
	a = b-a;


	a = a*b;
	b = a/b;
	a = a/b;


	a = a/b;
	b = a*b;
	a = b/a;


	a = a^b;
	b = a^b;
	a = a^b;
	sau 
	a ^=b;
	b ^=a;
	a ^=b;
	*/
}