#include<iostream>
using namespace std;

void swapInput(char input[],char swapedInput[]) {
	int counter = 0;
	while (input[counter] != '\0') {
		counter++;
	}
	counter--;
	int i;
	for (i = 0;input[i] != '\0';i++,counter--) {
		swapedInput[i] = input[counter];
	}
	swapedInput[i] = '\0';
}
bool doExist_(char* symbols, char* word) {
	char swapedInput[100];
	bool sameWord = true;
	swapInput(symbols, swapedInput);
	for (int i = 0;swapedInput[i] != '\0';i++) {
		if (swapedInput[i] == word[0]) {
			for (int j = i, k = 0;word[k] != '\0';j++, k++) {
				if (swapedInput[j] != word[k]) {
					sameWord = false;
					break;
				}
			}
		}
	}
	if (sameWord == true) {
		return true;
	}
	return false;

}
int* CheckNums(long num1, long num2) {
	int numbers[10000];
	int i_numbers = 0;
	int digit1;
	int digit2;
	long copyOfnum2;
	while (num1 != 0) {
		digit1 = num1 % 10;
		copyOfnum2 = num2;
		while (copyOfnum2  != 0) {
			digit2 = copyOfnum2 % 10;
			if (digit1 == digit2) {
				numbers[i_numbers] = digit1;
				i_numbers++;
			}
			copyOfnum2 /= 10;
		}
		num1 /= 10;
	}
	return numbers;
}
int strLen(char input[]) {
	int counter = 0;
	for (counter;input[counter] != '\0';counter++);
	return counter;
}
long getWords(char str[])
{
	long count = 0;
	long strLength = strLen(str);

	int currentPosition = 0;

	char words[100][100]{ 0 };

	if (strLength == 0)
		return -1;

	for (int i = 0; i <= strLen(str); i++)
	{
		if (str[i] != ' ' && str[i] != '\t' && str[i] != '\0')
		{
			words[count][currentPosition] = str[i];
			currentPosition++;
		}
		else if ((str[i] == ' ' || str[i] == '\t' || str[i] == '\0') && str[i - 1] != '\t' && str[i - 1] != ' ')
		{
			count++;
			currentPosition = 0;
		}
	}

	for (int i = 0; i < count; i++)
	{
		std::cout << words[i] << "-";
	}


	return count;

}
int lenghtOfNumber(long number) {
	int digit = 0;
	while (number != 0) {
		number /= 10;
		digit++;

	}
	return digit;
}
int convertNumber(long num) {
	int sum = 0;
	while (num != 0) {
		sum += num % 10;
		num /= 10;
	}
	return sum;
}
void reverse(char input[]) {
	int difference = abs('a' - 'A');
	//cout << difference << endl;
	for (int i = 0;input[i] != '\0';i++) {
		if ((input[i] >= 'a' && input[i] <= 'z') || (input[i] >= 'A' && input[i] <= 'Z')) {
			if (input[i] >= 'A'&& input[i] <= 'Z') {
				input[i] += difference;
				cout << input[i];
			}
			else {
				input[i] -= difference;
				cout << input[i];
			}
		}
	}
	//return input;
}
bool doExist(char* symbols, char* word) {
	bool notSameWord = false;
	for (int i = 0;symbols[i] != '\0';i++) {
		if (symbols[i] == word[0]) {
			for (int j = 0,k=i;word[j] != '\0'&& symbols[i] != '\0';j++, k++) {
				notSameWord = false;
				if (word[j] != symbols[k]) {
					notSameWord = true;
					break;
				}
			}
		}
	}
	if (notSameWord == true) {
		return false;
	}
	else {
		return true;
	}
}
int DigitPos(long num, int k) {
	int digit = -1;
	if (k > lenghtOfNumber(num)) {
		return -1;
	}
	else {
		digit = num / pow(10, (lenghtOfNumber(num) - k));
		digit = digit % 10;
		return digit;
	}
}
/*bool CheckDate(char input[]) {
	int days=0;
	int months = 0;
	int i = 0;
	if (strLen(input) > 5) {
		return false;
	}
	for (i = 0;input[i] != '.';i++) {
		days += input[i] - '0';
	}
	for (i = i + 1;input[i] != '\0';i++) {
		months += input[i] - '0';
	}
	if (months == 1) {
		if (days > 31) {
			return false;
		}
	}
	if (months == 2) {
		if (days > 29) {
			return false;
		}
	}
	if (months == 3) {
		if (days > 31) {
			return false;
		}
	}
	if (months == 4) {
		if (days > 30) {
			return false;
		}
	}

}*/
void arrayOfIntNumbers(int num1[], int num2[],int size1,int size2) {
	int sameNumbers[100];
	int sortedArr[100];
	int i_sameNumbers = 0;
	for (int i = 0;i < size1;i++) {
		for (int j = 0;j < size2;j++) {
			if (num1[i] == num2[j]) {
				sameNumbers[i_sameNumbers] = num1[i];
				i_sameNumbers++;
			}
		}
	}
	int temp;
	for (int i = 0;i < i_sameNumbers-1;i++) {
		for (int j = i+1;j < i_sameNumbers;j++) {
			if (sameNumbers[i] > sameNumbers[j]) {
				temp = sameNumbers[i];
				sameNumbers[i] = sameNumbers[j];
				sameNumbers[j] = temp;
			}
		}
	}
	for (int i = 0;i < i_sameNumbers;i++) {
		cout << sameNumbers[i] << " ";
	}
}
void rectangle(int n, int m, char p) {
	char rectangleArr [100][100];
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			rectangleArr[i][j] = p;
			cout << rectangleArr[i][j];
		}
		cout << endl;
	}
}
int sumOfDiagonal(int n, int arr[][100]) {
	int sum=0;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			if (j > i) {
				sum += arr[i][j];
			}
		}
	}
	return sum;
}
void transponate(int matrix[][100],int n) {
	int transponatedMatrix[100][100] { 0 };
	cout << endl;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			transponatedMatrix[i][j] = matrix[j][i];
			cout << transponatedMatrix[i][j] << " ";
		}
		cout << endl;
	}
}
void multuplyingMatrix(int** matrix1, int** matrix2, int size) {
	int** multiply = new int* [size];
	for (int i = 0;i < size;i++) {
		multiply[i] = new int[size];
	}
	for (int i = 0;i < size;i++) {
		for (int j = 0;j < size;j++) {
			multiply[i][j] = 0;
			for (int k = 0;k < size;k++) {
				multiply[i][j] += matrix1[i][k] * matrix2[k][j];
			}

		}
	}
	cout << endl;
	for (int i = 0;i < size;i++) {
		for (int j = 0;j < size;j++) {
			cout << multiply[i][j] << " ";
		}
		cout << endl;
	}
}
void bubbleSort(int arrayInt[],int size) {
	int swap = 0;
	for (int i = 0;i < size;i++) {
		swap = 0;
		for (int j = i + 1;j < size;j++) {
			if (arrayInt[i] > arrayInt[j]) {
				swap = arrayInt[i];
				arrayInt[i] = arrayInt[j];
				arrayInt[j] = swap;
			}
		}
	}
	for (int i = 0;i < size;i++) {
		cout << arrayInt[i] << " ";
	}
}
void swapElements(int array[], int size, int start, int end) {
	int swap;
	for (int i = start,j=end;i <= (start + end) / 2;i++,j--) {
		swap = array[i];
		array[i] = array[j];
		array[j] = swap;
		swap = 0;
	}
	cout << endl;
	for (int i = 0;i < size;i++) {
		cout << array[i] << " ";
	}

}
void transformateNumbers(char input[]) {
	for (int i = 0;input[i] != '\0';i++) {
		if (input[i] >= '0' && input[i] <= '9') {
			input[i] = '9' - input[i] +'0';
		}
	}
	for (int i = 0;input[i] != '\0';i++) {
		cout << input[i];
	}
}
void multiplyMatrixAgain(int** matrix1, int** matrix2, int size) {
	int** answer = new int* [size];
	for (int i = 0;i < size;i++) {
		answer[i] = new int[size];
	}
	for (int i = 0;i < size;i++) {
		for (int j = 0;j < size;j++) {
			answer[i][j] = 0;
			for (int k = 0;k < size;k++) {
				answer[i][j] += matrix1[i][k] * matrix2[k][j];
			}

		}
	}
	for (int i = 0;i < size;i++) {
		for (int j = 0;j < size;j++) {
			cout << answer[i][j] << " ";
		}
		cout << endl;
	}
}