Main Idea: Instead of directly comparing permutations,I transformed each permutation and required permutation into a number that allows prefix matching efficiently.After doing i just have to find the permutation which is nearest to reruired permutation .

Complexity: O(n * m * log n) ~~~~~

include <bits/stdc++.h>

using namespace std;

define int long long

const int BASE = 11;

/* Find how many digits are different from the back while comparing hashes */ int common(int x,int y){

int cnt=0;

while(x!=y){
    x/=BASE;
    y/=BASE;
    cnt++;
}

return cnt;

}

/* Binary search the closest hash and return minimum mismatch count */ int best(int n,vector &a,int m){

int st=0,end=a.size()-1;

while(st<=end){

    int mid=(st+end)/2;

    if(a[mid]<=n){
        st=mid+1;
    }
    else{
        end=mid-1;
    }
}

int ans=m;

// check upper bound candidate
if(st<a.size()){
    ans=min(ans,common(n,a[st]));
}

// check lower bound candidate
if(end>=0){
    ans=min(ans,common(n,a[end]));
}

return ans;

}

int32_t main() {

int t;
cin>>t;

while(t--){

    int n,m;
    cin>>n>>m;

    vector<int> equ(n),req(n);

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

        vector<int> a(m);

        for(int j=0;j<m;j++){
            cin>>a[j];
            a[j]--;
        }

        /*
            temp  -> original permutation hash
            treq  -> inverse permutation hash
        */

        int temp=0,treq=0;

        // create original permutation hash
        for(int j=0;j<m;j++){
            temp=temp*BASE+a[j];
        }

        // build inverse permutation
        vector<int> pos(m);

        for(int j=0;j<m;j++){
            pos[a[j]]=j;
        }

        // create inverse permutation hash
        for(int j=0;j<m;j++){
            treq=treq*BASE+pos[j];
        }

        req[i]=temp;
        equ[i]=treq;
    }

    // sort inverse hashes for binary search
    sort(equ.begin(),equ.end());

    vector<int> ans(n);

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

        int cnt=best(req[i],equ,m);

        // matched prefix length
        ans[i]=m-cnt;
    }

    for(int i=0;i<n;i++){
        cout<<ans[i]<<" ";
    }

    cout<<endl;
}

} ~~~~~

374473747