#include<bits/stdc++.h>

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

{

    // making pair for <<i,j>time>

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

    //visited for checking already rotten or not

    int vis[n][m];

    //counting fresh oranges and pushing rotting oranges positon with 0 time in queue.

    //also marking visited rotten oranges

    int cntFresh=0;

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

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

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

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

                vis[i][j] = 2;

            }

            else {

                vis[i][j]=0;

            }

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

            cntFresh++;

        }

    }

    int tm = 0;//max time

    int drow[] = {-1,0,1,0};//for update row:  up   same down same

    int dcol[] = {0,1,0,-1};//for update col: same  next same previous

    int cnt=0;//counting that all fresh oranges now rotted or not 

    while(!q.empty()) {

        int r = q.front().first.first;//taking rotted row

        int c = q.front().first.second;//taking rotted col

        int t = q.front().second;//time

        tm = max(tm,t);//max time, updating every time

        q.pop();

        //checking all neighbours for every rotted oranges.

        //updating time with 1

        //and pushing in queue which we are rotting, makring visited

        //counting no of rotted oranges that converted from fresh 

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

            int nrow = r + drow[i];

            int ncol = c + dcol[i];

            if(nrow>=0 && nrow<n && ncol>=0 && ncol<m 

            && vis[nrow][ncol]!=2 && grid[nrow][ncol]!=0 && grid[nrow][ncol]==1) {

                q.push({{nrow, ncol}, t+1});

                vis[nrow][ncol]=2;

                cnt++;//counting no of rotted oranges that converted from fresh 

            }

        }

    }

    // at last if all fresh oranges converted into rotten then cnt==cntfresh return tm else -1 

    if(cnt != cntFresh) return -1;

    return tm;

}

#include<bits/stdc++.h>

using namespace std;

vector<int> printLeftView(BinaryTreeNode<int> *root)

{

    queue<BinaryTreeNode<int>*>q;

    q.push(root);

    vector<int>v;

    while(!q.empty()){

        int n=q.size();

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

        BinaryTreeNode<int>*cur=q.front();

        q.pop();

        if(i==0)

        v.push_back(cur->data);

        if(cur->left){

            q.push(cur->left);

        }

        if (cur->right) {

            q.push(cur->right);

        }

        }

    }

    return v;

    }

vector<int> getLeftView(TreeNode<int> *root)

{

    //    Write your code here

    queue<TreeNode<int>*>q;

    vector<int>v;

    if(root==NULL)

    return v;

    q.push(root);//q ki size 1 hai.

    while(!q.empty()){

        int n=q.size();//har level ka size n me store krte hai har bar.

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

         TreeNode<int>*cur=q.front();

         q.pop();

         if(i==0){//jb nye level pr jate hai to uska 1st element left view hoga.

             v.push_back(cur->data);

         }

         if(cur->left){

             q.push(cur->left);

         }

         if(cur->right)

         q.push(cur->right);

        }

    }

    return v;

}

vector<int> getLeftView(TreeNode<int> *root)

{

    //    Write your code here

    queue<TreeNode<int>*>q;

    vector<int>v;

    if(root==NULL)

    return v;

    q.push(root);//q ki size 1 hai.

    while(!q.empty()){

        int n=q.size();//har level ka size n me store krte hai har bar.

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

         TreeNode<int>*cur=q.front();

         q.pop();

         if(i==0){//jb nye level pr jate hai to uska 1st element left view hoga.

             v.push_back(cur->data);

         }

         if(cur->left){

             q.push(cur->left);

         }

         if(cur->right)

         q.push(cur->right);

        }

    }

    return v;

}

Node* sortList(Node *head){

    // Write your code here.

    Node * temp=head;

    stack<int>st;

    while(temp){

        if(temp->data==2)

         st.push(temp->data);

         temp=temp->next;

    }

    temp=head;

    while(temp){

        if(temp->data==1)

         st.push(temp->data);

         temp=temp->next;

    }

    temp=head;

    while(temp){

        if(temp->data==0)

         st.push(temp->data);

         temp=temp->next;

    }

    temp=head;

    while(!st.empty()){

        temp->data=st.top();

        st.pop();

        temp=temp->next;

    }

    return head;

}

#include<stack>

using namespace std;

class Browser

{

    string cur;

    stack<string>st1;

    stack<string>st2;

    public:

    Browser(string &homepage)

    {   

        cur =homepage;

        // Write you code here

    }

    void visit(string &url)

    { 

        st1.push(cur);

        cur=url;

        while(!st2.empty()){

            st2.pop();

        }

        // stack<string>temp;

        // st2=temp;

        // Write you code here

    }

    string back(int steps)

    {

     while(steps>0 && st1.empty()==false){

         st2.push(cur);

         cur=st1.top();

         st1.pop();

         steps--;

     }

     return cur;

        // Write you code here

    }

    string forward(int steps)

    {

        while(steps>0 && st2.empty()==false){

            st1.push(cur);

            cur=st2.top();

            st2.pop();

            steps--;

        }

        return cur;

        // Write you code here

    }

};

#include<bits/stdc++.h>

using namespace std;

class Queue {

    // Define the data members(if any) here.

    stack<int>s1,s2;

    public:

    Queue() {

        // Initialize your data structure here.

    }

    void enQueue(int val) {

        s1.push(val);

        // Implement the enqueue() function.

    }

    int deQueue() {

        if(s1.empty()){

            return -1;

        }

        else{

            while(!s1.empty()){

                s2.push(s1.top());

                s1.pop();

            }

           int x= s2.top();

           s2.pop();

           while(!s2.empty()){

                s1.push(s2.top());

                s2.pop();

            }

            return x;

        }

        // Implement the dequeue() function.

    }

    int peek() {

        if(s1.empty()){

            return -1;

        }

        else{

            while(!s1.empty()){

                s2.push(s1.top());

                s1.pop();

            }

           int x= s2.top();

           while(!s2.empty()){

                s1.push(s2.top());

                s2.pop();

            }

           return x;

           }

        // Implement the peek() function here.

    }

    bool isEmpty() {

        if(s1.empty()){

            return true;

        }

        else{

            return false;

        }

        // Implement the isEmpty() function here.

    }

};

#include<bits/stdc++.h>

using namespace std;

void helpSort(stack<int>&s,int num){

    if(s.empty() || s.top()>num ){

        s.push(num);

        return; 

    }

    int item=s.top();

    s.pop();

    helpSort(s, num) ;

    s.push(item);

}

void sortStack(stack<int>&s){

    if(s.empty()){

        return;

    }

    int num=s.top();

    s.pop();

    sortStack(s);

    helpSort(s,num);

}

// void sortStack(stack<int> &stack)

// {

//  // Write your code here

//  vector<int>v(stack.size());

//  int i=0;

//  while(!stack.empty()){

//      v[i]=stack.top();

//      stack.pop();

//      i++;

//  }

//  sort(v.begin(),v.end());

//  for(int i=v.size()-1;i>=0;i--){

//      stack.push(v[i]);

//  }

// }

#include<bits/stdc++.h>

string reverseString(string &str) {

    stack<string> st;

    for (int i = 0; i < str.length();) {

        // Skip leading spaces

        while (i < str.length() && str[i] == ' ') {

            i++;

        }

        // Extract the word

        string c = "";

        while (i < str.length() && str[i] != ' ') {

            c += str[i];

            i++;

        }

        if (!c.empty()) {

            st.push(c);

        }

    }

    string s;

    while (!st.empty()) {

        s += st.top();

        s += " ";

        st.pop();

    }

    // Remove the trailing space

    if (!s.empty()) {

        s.pop_back();

    }

    return s;

}