const int mod = 1e9+7;
void multiply(long long int F[2][2], long long int M[2][2]);
void power(long long int F[2][2], long long int n);

int fib(long long int n)
{
    long long int F[2][2] = {{1, 1}, {1, 0}};
    if (n == 0) return 0;
    power(F, n - 1);
    return F[0][0];
}
void power(long long int F[2][2], long long int n)
{
    if(n == 0 || n == 1) return;

    long long int M[2][2] = {{1, 1}, {1, 0}};
    
    power(F, n / 2);
    multiply(F, F);
    
    if (n % 2 != 0)
        multiply(F, M);
}
void multiply(long long int F[2][2], long long int M[2][2])
{
    int x = ((F[0][0]%mod * M[0][0]%mod)%mod + (F[0][1]%mod * M[1][0]%mod)%mod)%mod;
    int y = ((F[0][0]%mod * M[0][1]%mod)%mod + (F[0][1]%mod * M[1][1]%mod)%mod)%mod;
    int z = ((F[1][0]%mod * M[0][0]%mod)%mod + (F[1][1]%mod * M[1][0]%mod)%mod)%mod;
    int w = ((F[1][0]%mod * M[0][1]%mod)%mod + (F[1][1]%mod * M[1][1]%mod)%mod)%mod;
    
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}
// call using fib(n)

#include<iostream>
using namespace std;

class MATRIX{
    int row;
    int col;
    int **array;
    public:
    MATRIX();
    MATRIX(const MATRIX&);
    MATRIX(int,int);
    void takeinput();
    MATRIX operator+(MATRIX);
    MATRIX operator-(MATRIX);
    bool operator==(MATRIX);
    friend ostream& operator<<(ostream&,MATRIX);
    ~MATRIX();
};
int main(){

    int r,c;
    cout<<"Enter number of rows for matrix m1: ";
    cin>>r;
    cout<<"Enter number of columns for matrix m1: ";
    cin>>c;
    MATRIX m1(r,c);
    m1.takeinput();
    cout<<"Enter number of rows for matrix m2: ";
    cin>>r;
    cout<<"Enter number of columns for matrix m2: ";
    cin>>c;
    MATRIX m2(r,c);
    m2.takeinput();
    cout<<"Matrix m1 :-"<<endl<<m1;
    cout<<"Matrix m2 :-"<<endl<<m2;
    MATRIX m3,m4;
    if(m1==m2){
        MATRIX m3 = m1 + m2;
        cout<<"Matrix m3 :-"<<endl;
        cout<<m3;
        MATRIX m4 = m1 - m2;
        cout<<"Matrix m4 :-"<<endl;
        cout<<m4;
    }
    else{
        cout<<"Error! The dimensions of both the operand matrices are not same\n";
    }
    return 0;
}

MATRIX::MATRIX(int r,int c){
    row = r;
    col = c;
    array = new int*[r];
    for(int i=0;i<r;i++){
        array[i] = new int[c];
        for(int j=0;j<c;j++) {
            array[i][j] = 0;
        }
    }
}
MATRIX::MATRIX(const MATRIX& obj){
    row = obj.row;
    col = obj.col;
    array = new int*[row];
    for(int i=0;i<row;i++){
        array[i] = new int[col];
        for(int j=0;j<col;j++){
            array[i][j] = obj.array[i][j];
        }
    }
}
void MATRIX::takeinput(){
    for(int i=1;i<=row;i++){
        for(int j=1;j<=col;j++){
            cout<<"Enter ("<<i<<", "<<j<<") element: ";
            cin>>array[i-1][j-1];
        }
    }
}
MATRIX::MATRIX(){
    row=0;
    col=0;
    array=NULL;
}
MATRIX MATRIX::operator+(MATRIX m2){
    MATRIX output(row,col);
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            output.array[i][j] = array[i][j] + m2.array[i][j];
        }
    }
    return output;
}
MATRIX MATRIX::operator-(MATRIX m2){
    MATRIX output(row,col);
    for(int i=0;i<row;i++){
        for(int j=0;j<col;j++){
            output.array[i][j] = array[i][j] - m2.array[i][j];
        }
    }
    return output;
}
ostream& operator<<(ostream &print, MATRIX m){
    for(int i=0;i<m.row;i++){
        for(int j=0;j<m.col;j++){
            print<<m.array[i][j]<<" ";
        }
        print<<endl;
    }
    return print;
}
bool MATRIX::operator==(MATRIX m2){
    return (row==m2.row && col==m2.col) ? true:false;
}

MATRIX::~MATRIX(){
    for(int i=0;i<row;i++){
        delete []array[i];
    }
    delete []array;
}

def spiral(matrix, r, c):
    circular = []
    
    start_row, end_row = 0, r
    start_col, end_col = 0, c
    
    while start_row < end_row and start_col < end_col:
    
        for i in range(start_col, end_col):
            circular.append(matrix[start_row][i])
        start_row += 1
        
        for i in range(start_row, end_row):
            circular.append(matrix[i][end_col-1])
        end_col -= 1
        
        for i in range(end_col, start_col, -1):
            circular.append(matrix[end_row-1][i-1])
        end_row -= 1
        
        for i in range(end_row, start_row, -1):
            circular.append(matrix[i-1][start_col])
        start_col += 1
    
    return circular

class Solution 
{
    //Function to find minimum number of operations that are required 
    //to make the matrix beautiful.
    static int findMinOperation(int matrix[][], int n)
    {
        int sumRow[] = new int[n];
        int sumCol[] = new int[n];
        Arrays.fill(sumRow, 0);
        Arrays.fill(sumCol, 0);
        
        //calculating sumRow[] and sumCol[] array.
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                sumRow[i] += matrix[i][j];
                sumCol[j] += matrix[i][j];
                  
            }
        }
        
        //finding maximum sum value in either row or in column.
        int maxSum = 0;
        for (int i = 0; i < n; ++i)
        {
            maxSum = Math.max(maxSum, sumRow[i]);
            maxSum = Math.max(maxSum, sumCol[i]);
        } 
        
        int count = 0;
        for (int i = 0, j = 0; i < n && j < n;) 
        {
            //finding minimum increment required in either row or column.
            int diff = Math.min(maxSum - sumRow[i], maxSum - sumCol[j]);
            
            //adding difference in corresponding cell, 
            //sumRow[] and sumCol[] array.
            matrix[i][j] += diff;
            sumRow[i] += diff;
            sumCol[j] += diff;
            
            //updating the result.
            count += diff;
            
            //if ith row is satisfied, incrementing i for next iteration.
            if (sumRow[i] == maxSum)
                ++i;
            
            //if jth column is satisfied, incrementing j for next iteration.
            if (sumCol[j] == maxSum)
                ++j;
        }
        //returning the result.
        return count;
    }
}

class Solution
{
    //Function to modify the matrix such that if a matrix cell matrix[i][j]
    //is 1 then all the cells in its ith row and jth column will become 1.
    void booleanMatrix(int matrix[][])
    {
        int r = matrix.length;
        int c = matrix[0].length;

        //using two list to keep track of the rows and columns 
        //that needs to be updated with 1.
        int row[] = new int[r];
        int col[] = new int[c];
        
        for(int i = 0; i < r; i++)
        {
            for(int j = 0; j < c; j++)
            {
                //if we get 1 in matrix, we mark ith row and jth column as 1.
                if(matrix[i][j] == 1){
                    row[i] = 1;
                    col[j] = 1;
                }  
            }
        }
        
        for(int i =0; i < r; i++)
        {
            for(int j = 0; j < c; j++)
            {
                //if ith row or jth column is marked as 1, then all elements
                //of matrix in that row and column will be 1.
                if(row[i] == 1 || col[j] == 1){
                    matrix[i][j] = 1;
                }
            }
        }
    }
}

class Solution
{
    //Function to interchange the rows of a matrix.
    static void interchangeRows(int matrix[][])
    {
       for(int i=0;i<matrix.length/2;i++){
           for(int j=0;j<matrix[i].length;j++){
               int temp=matrix[i][j];
               matrix[i][j]=matrix[matrix.length-i-1][j];
               matrix[matrix.length-i-1][j]=temp;
           }
       } 
    }
}

class Solution
{
    //Function to reverse the columns of a matrix.
    static void reverseCol(int matrix[][])
    {
       for(int i=0; i<matrix.length; i++){
           for(int j=0; j<matrix[i].length/2; j++)
           {
               int temp = matrix[i][j];
               matrix[i][j] = matrix[i][matrix[i].length-j-1];
               matrix[i][matrix[i].length-j-1] = temp;
           }
       } 
    }
}

class Solution
{
    //Function to exchange first column of a matrix with its last column.
    static void exchangeColumns(int matrix[][])
    {
       int temp = 0;
       for (int i=0; i<matrix.length; i++)
       {
            temp = matrix[i][0];
            matrix[i][0] = matrix[i][matrix[i].length-1];
            matrix[i][matrix[i].length-1] = temp; 
       }
    }
}

class Solution
{
    //Function to get cofactor of matrix[p][q] in temp[][]. 
    static void getCofactor(int matrix[][], int temp[][], int p, int q, int n)
    {
        int i = 0, j = 0;

        for (int row = 0; row < n; row++)
        {
            for (int col = 0; col < n; col++)
            {
                //copying only those elements into temporary matrix 
                //which are not in given row and column.
                if(row != p && col != q)
                {
                    temp[i][j++] = matrix[row][col];

                    //if row is filled, we increase row index and
                    //reset column index.
                    if(j == n - 1)
                    {
                        j = 0;
                        i++;
                    }
                }
            }
         }
    }
    
    
    //Function for finding determinant of matrix.
    static int determinantOfMatrix(int matrix[][], int n)
    {
        int D = 0; 

        //base case
        if (n == 1)
            return matrix[0][0];

        //creating a list to store Cofactors.
        int temp[][]  = new int[n][n];

        int sign = 1;

        //iterating for each element of first row.
        for (int i = 0; i < n; i++)
        {
            //getting Cofactor of matrix[0][i].
            getCofactor(matrix, temp, 0, i, n);
            D += sign * matrix[0][i] * determinantOfMatrix(temp, n - 1);

            //terms are to be added with alternate sign so changing the sign.
            sign = -sign;
        }
        //returning the determinant.
        return D;
    }
}

class Solution
{
    //Function to multiply two matrices.
    static int[][] multiplyMatrix(int A[][], int B[][])
    {
        int n1 = a.length;
        int m1 = a[0].length;
        int n2 = b.length;
        int m2 = b[0].length;
        
        if(m1!=n2)
        {
            int arr0[][] = new int[1][1];
            arr0[0][0] = -1;
            return arr0;
        }
        
        int arr[][] = new int[n1][m2];
        
        for(int i = 0 ; i<n1 ; i++)
        for(int j = 0 ; j<m2 ; j++)
        for(int q = 0; q<n2 ; q++)
        arr[i][j]+= a[i][q]*b[q][j];
        
        return arr;
    }
}

class Solution
{
    //Function to return sum of upper and lower triangles of a matrix.
    static ArrayList<Integer> sumTriangles(int matrix[][], int n)
    {
        ArrayList<Integer> list=new ArrayList<>();
        int sum1=0;
        int sum2=0;
        for(int g=0; g<matrix.length; g++){
            for(int i=0, j=g; j<matrix.length; i++,j++){
                sum1+=matrix[i][j];
            }
        }
        list.add(sum1);
        for(int g=0; g<matrix.length; g++){
            for(int i=g,j=0; i<matrix.length; i++,j++){
                sum2+=matrix[i][j];
            }
        }
        list.add(sum2);
        return list;
    }
}

class Solution
{
    //Function to add two matrices.
    static int[][] sumMatrix(int A[][], int B[][])
    {
        int n = A.length, m = A[0].length;
        int res[][] = new int[0][0];
        //Check if two input matrix are of different dimensions
        if(n != B.length || m != B[0].length)
            return res;
        
        res = new int[n][m];
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                res[i][j] = A[i][j] + B[i][j];
                
        return res;
    }
}

// Time Complexity : O(r * log(max - min) * logC)

import java.util.Arrays;

public class MedianInRowSorted
{
    static public int matMed(int mat[][], int r ,int c)
    {
    	int min = mat[0][0], max = mat[0][c-1];
    	for (int i=1; i<r; i++)
    	{
    		if (mat[i][0] < min)
    			min = mat[i][0];
    
    		if (mat[i][c-1] > max)
    			max = mat[i][c-1];
    	}
    
    	int medPos = (r * c + 1) / 2;
    	while (min < max)
    	{
    		int mid = (min + max) / 2;
    		int midPos = 0;
            int pos = 0;
    		for (int i = 0; i < r; ++i){
    			    pos = Arrays.binarySearch(mat[i],mid);
                    
                    if(pos < 0)
                        pos = Math.abs(pos) - 1;
                      
                    
                    else
                    {
                        while(pos < mat[i].length && mat[i][pos] == mid)
                            pos += 1;
                    }
                      
                    midPos = midPos + pos;
    		}
    		if (midPos < medPos)
    			min = mid + 1;
    		else
    			max = mid;
    	}
    	return min;
    }

    public static void main(String[] args)
    {
    	int r = 3, c = 5;
    	int m[][]= { {5,10,20,30,40}, {1,2,3,4,6}, {11,13,15,17,19} };
    	System.out.println("Median is " + matMed(m, r, c)); 
    	
    }
}

// Efficient Code : Time Complexity : O(R + C)
 
import java.util.*;
import java.io.*;
 
class GFG 
{ 
	static int R = 4, C = 4;

	static void search(int mat[][], int x)
	{
		int i  = 0, j = C - 1;

		while(i < R && j >= 0)
		{
			if(mat[i][j] == x)
			{
				System.out.println("Found at (" + i + ", " + j + ")");
				return;
			}
			else if(mat[i][j] > x)
			{
				j--;
			}
			else
			{
				i++;
			}
		}
		System.out.println("Not Found");
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{10, 20, 30, 40},
    				   {15, 25, 35, 45},
    				   {27, 29, 35, 45},
    				   {32, 33, 39, 50}};
    	int x = 29;	   

    	search(arr, x);

		
    } 
}
 
 
 
 
// Naive Code : Time Complexity : O(R * C)
 
	static int R = 4, C = 4;

	static void search(int mat[][], int x)
	{
		for(int i = 0; i < R; i++)
		{
			for(int j = 0; j < C; j++)
			{
				if(mat[i][j] == x)
				{
					System.out.println("Found at (" + i + ", " + j + ")");
					
					return;
				}
			}
		}

		System.out.println("Not Found");
	}

import java.util.*;
import java.io.*;

class GFG 
{ 
	static void printSpiral(int mat[][], int R, int C)
	{
		int top = 0, left = 0, bottom = R - 1, right = C - 1;

		while(top <= bottom && left <= right)
		{
			for(int i = left; i <= right; i++)
				System.out.print(mat[top][i] + " ");

			top++;

			for(int i = top; i <= bottom; i++)
				System.out.print(mat[i][right] + " ");
			
			right--;

			if(top <= bottom){
			for(int i = right; i >= left; i--)
				System.out.print(mat[bottom][i] + " ");

			bottom--;
			}

			if(left <= right){
			for(int i = bottom; i >= top; i--)
				System.out.print(mat[i][left] + " ");

			left++;
			}			
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	printSpiral(arr, 4, 4);
    } 
}

// Efficient Code : Time Complexity : O(n^2), Auxiliary Space : O(1)
 
import java.util.*;
import java.io.*;
 
class GFG 
{ 
	static int n = 4;

	static void swap(int mat[][], int i, int j)
	{
			int temp = mat[i][j];
			mat[i][j] = mat[j][i];
			mat[j][i] = temp;
	}
	
	static void swap2(int low, int high, int i, int mat[][])
	{
	    	int temp = mat[low][i];
			mat[low][i] = mat[high][i];
			mat[high][i] = temp;
	}

	static void rotate90(int mat[][])
	{
		// Transpose
		for(int i = 0; i < n; i++)
			for(int j = i + 1; j < n; j++)
				swap(mat, i, j);
      
		// Reverse columns		
		for(int i = 0; i < n; i++)
		{
		    int low = 0, high = n - 1;
		    
		    while(low < high)
		    {
		        swap2(low, high, i, mat);
		        
		        low++;
		        high--;
		    }
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	rotate90(arr);

    		for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
				{
					System.out.print(arr[i][j]+" ");
				}

				System.out.println();
			}	
    }
}
 
 
 
 
// Naive Code : Time Complexity : O(n^2), Space Complexity : O(n^2)
 
	static int n = 4;

	static void rotate90(int mat[][])
	{
		int temp[][] = new int[n][n];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				temp[n - j - 1][i] = mat[i][j];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				mat[i][j] = temp[i][j];

	}

// last column becomes first row
// second last column becomes second row

// Efficient Code : Without Using Auxiliary Array

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int n = 4;

	static void swap(int mat[][], int i, int j)
	{
			int temp = mat[i][j];
			mat[i][j] = mat[j][i];
			mat[j][i] = temp;
	}

	static void transpose(int mat[][])
	{

		for(int i = 0; i < n; i++)
			for(int j = i + 1; j < n; j++)
				swap(mat, i, j);
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	transpose(arr);

    		for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
				{
					System.out.print(arr[i][j]+" ");
				}

				System.out.println();
			}	
    } 
}




// Naive Code : 

	static int n = 4;

	static void transpose(int mat[][])
	{
		int temp[][] = new int[n][n];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
              	// copy
				temp[i][j] = mat[j][i]; // temp[i][j] = mat[i][j];

		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
              	// copy back to original array
				mat[i][j] = temp[i][j];

	}

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int R = 4, C = 4;

	static void bTraversal(int mat[][])
	{
		if(R == 1)
		{
			for(int i = 0; i < C; i++)
				System.out.print(mat[0][i] + " ");
		}
		else if(C == 1)
		{
			for(int i = 0; i < R; i++)
				System.out.print(mat[i][0] + " ");
		}
		else
		{
			for(int i = 0; i < C; i++)
				System.out.print(mat[0][i] + " ");
			for(int i = 1; i < R; i++)
				System.out.print(mat[i][C - 1] + " ");
			for(int i = C - 2; i >= 0; i--)
				System.out.print(mat[R - 1][i] + " ");
			for(int i = R - 2; i >= 1; i--)
				System.out.print(mat[i][0] + " ");
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	bTraversal(arr);
    } 
}

import java.util.*;
import java.io.*;

class GFG 
{ 
	static int R = 4, C = 4;
	static void printSnake(int mat[][])
	{
		for(int i = 0; i < R; i++)
		{
			if(i % 2 == 0)
			{
				for(int j = 0; j < C; j++)
					System.out.print(mat[i][j] + " ");
			}
			else
			{
				for(int j = C - 1; j >= 0; j--)
					System.out.print(mat[i][j] + " ");
			}
		}
	}

	public static void main(String args[]) 
    {
        int arr[][] = {{1, 2, 3, 4},
    				   {5, 6, 7, 8},
    				   {9, 10, 11, 12},
    				   {13, 14, 15, 16}};

    	printSnake(arr);
    } 
}