#include<bits/stdc++.h>

int minTimeToRot(vector<vector<int>>& grid, int n, int m)

{

    vector<pair<int,int>> help={{0,1},{1,0},{-1,0},{0,-1}};

    queue<pair<pair<int,int>,int>> q;

    for(int i=0;i<n;i++){

        for(int j=0;j<m;j++){

            if(grid[i][j]==2){

                q.push({{i,j},0});

            }

        }

    }

    vector<vector<int>> visited(n,vector<int>(m,0));

    int ans=0;

    while(!q.empty()){

        pair<pair<int,int>,int> node=q.front();

        q.pop();

        int x=node.first.first;

        int y=node.first.second;

        // cout<<x<<" "<<y<<endl;

        int time=node.second;

       ans=time;

        visited[x][y]=1;

        int new_time=time+1;

        for(int i=0;i<4;i++){

            int new_x=help[i].first+x;

            int new_y=help[i].second+y;

            if(new_x>=0 && new_y>=0 && new_x<n && new_y<m && grid[new_x][new_y]==1 && visited[new_x][new_y]!=1){

                grid[new_x][new_y]=2;

                pair<pair<int,int>,int> l={{new_x,new_y},new_time};

                q.push(l);

            }

            if(new_x>=0 && new_y>=0 && new_x<n && new_y<m){

            visited[new_x][new_y]=1;

            }

        }

    }

        for(int i=0;i<n;i++){

            for(int j=0;j<m;j++){

                if(grid[i][j]==1){

                    return -1;

                }

            }

        }

        return ans;

    // Write your code here. 

}

#include<bits/stdc++.h>

void dfs(int node, vector<vector<int>> &adj, vector<bool> &visited, stack<int>&s){

    visited[node]=true;

    for(auto i : adj[node]){

        if(!visited[i]){

            dfs(i,adj,visited,s);

        }

    }

    s.push(node);

}

int dfs3(int node, vector<vector<int>> &adjR, vector<bool> &visited){

    visited[node]=true;

    int k=1;

    int ans=1;

    for(auto i:adjR[node]){

        if(!visited[i]){

            k=k+1;

            ans+=dfs3(i,adjR,visited);

        }

    }

    return ans;

}

int countWays(int n, vector<vector<int>> &fruitIds)

{

    vector<vector<int>> adj(n);

    for(int i=0;i<fruitIds.size();i++){

        int u=fruitIds[i][0];

        int v=fruitIds[i][1];

        adj[u].push_back(v);

        adj[v].push_back(u);

    }

    vector<bool> visited(n);

    stack<int> s;

    for(int i=0;i<n;i++){

        if(!visited[i]){

            dfs(i,adj,visited,s);

        }

    }

    // REVERSE THE GRAPH TO FIND ALL THE SCC

    vector<vector<int>> adjR(n);

    for(int i=0;i<n;i++){

        visited[i]=false;

    }

    vector<int> arr; int num=0; 

    while(!s.empty()){

        int node=s.top();

        s.pop();

        if(!visited[node]){

            num=dfs3(node,adj,visited);

            arr.push_back(num);

        }

    }

    int sum=0;

    int product=1;

    sort(arr.begin(),arr.end());

    for(int i=0;i<arr.size();i++){

        for(int j=i+1;j<arr.size();j++){

            product=arr[i]*arr[j];

            sum+=product;

        }

    }

    return sum;

    // Write your code here.

}

#include <bits/stdc++.h> 

int twoSum(vector<int> arr,int l,int target){

    int r=arr.size()-1;

    int ans=0;

    while(l<=r){

        if(arr[l]+arr[r]<target){

            ans+=(r-l);

            l++;

            r=arr.size()-1;

        }

        else{

            r--;

        }

    }

    return ans;

}

int threeSumSmaller(int n, vector<int> arr, int target) {

    if(arr.size()<3){

        return 0;

    }

    sort(arr.begin(),arr.end());

    int ans=0;

    for(int i=0;i<=n-3;i++){

        // if(i!=0 && arr[i-1]==arr[i]){

        //     continue;

        // }

            int num=target-arr[i];

            ans+=twoSum(arr,i+1,num);

    }

    return ans;

    // Write your code here.

}

#include <bits/stdc++.h>

int solve(int i, int j, int n, int m, vector<string> &grid, string &s, int p,vector<vector<int>>&visited) {

        if(i<0|| j<0||i>n||j>m){

            return 0;

        }

        // cout<<s[k];

        if(p==s.size()-1 && grid[i][j]==s[p]){

            visited[i][j]=-1;

            return 1;

        }

        int ans=0;

        visited[i][j]=0;

        vector<pair<int,int>> help{{1,0},{0,1},{0,-1},{-1,0}};

        for(int k=0;k<4;k++){

            int new_i=i+help[k].first;

            int new_j=j+help[k].second;

            if(new_i>=0 && new_j>=0 && new_i<n && new_j<m && grid[new_i][new_j]==s[p+1]&&visited[new_i][new_j]!=0){

                // cout<<grid[new_i][new_j]<<endl;

                visited[new_i][new_j]=0;

                ans+=solve(new_i,new_j,n,m,grid,s,p+1,visited);

            }

        }

        visited[i][j]=-1;

        return ans;

}

int countStrings(int n, int m, vector<string> &grid , string &s)

{

    vector<vector<int>> visited(n);

    for(int i=0;i<n;i++){

        for(int j=0;j<m;j++){

            visited[i].push_back(-1);

        }

    }

    int ans=0;

    for(int i=0;i<n;i++){

        for(int j=0;j<m;j++){

                  if (grid[i][j] == s[0]) {

                    ans += solve(i, j, n, m, grid, s, 0,visited);

                  }

                }

    }

    return ans;

    // Write your code here

}

#include <bits/stdc++.h> 

vector<int> mergeKSortedArrays(vector<vector<int>>&kArrays, int k)

{

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

    vector<pair<int,vector<int>>> help; 

    for(int i=0;i<k;i++){

      help.push_back({0, kArrays[i]});

      pq.push({kArrays[i][0], i});

    }   

    vector<int> ans;

    while(!pq.empty()){

        pair<int,int> temp=pq.top();

        pq.pop();

        int arrnum=temp.second;

        ans.push_back(temp.first);

        vector<int> temp1=kArrays[arrnum];

        int index=help[arrnum].first+1;

        if(index>=temp1.size()){

            continue;

        }

        else{

            help[arrnum]={index,temp1};

            pq.push({temp1[index],arrnum});

        }

    }

    return ans;

    // Write your code here. 

}