#pragma GCC target ("avx2") #pragma GCC optimize ("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize ("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include #include using namespace __gnu_pbds; using namespace std; #define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) #define endl '\n' typedef long long ll; #define mod1 (ll)1000000007 #define mod2 (ll)998244353 #define int ll #define pll pair typedef long double lb; typedef tree< pair, null_type, less>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define eps (lb)(1e-9) struct custom_hash { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; // Operator overloads template // cin >> pair istream& operator>>(istream &istream, pair &p) { return (istream >> p.first >> p.second); } template // cin >> vector istream& operator>>(istream &istream, vector &v) { for (auto &it : v) cin >> it; return istream; } template // cout << pair ostream& operator<<(ostream &ostream, const pair &p) { return (ostream << p.first << " " << p.second); } template // cout << vector ostream& operator<<(ostream &ostream, const vector &c) { for (auto &it : c) cout << it << " "; return ostream; } // Utility functions template void print(T &&t) { cout << t << "\n"; } template void print(T &&t, Args &&... args) { cout << t << " "; print(forward(args)...); } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ll random(ll p){ // gives random number in [0,p] return uniform_int_distribution(1<<19, p)(rng); } int AL = 9; ll n; vectorpp((1<<20),0); vectorv; template struct StringHash{ StringHash(const vector &s){} int hashval(int l1,int r2){ return 0; } pll gib(ll l,ll r){ return {0,0}; } int compare(int l1,int r1,int l2,int r2){ return true; } }; template struct StringHash{ public: StringHash(){} int modpow(ll x,ll p){ ll ans = 1; while(p){ if(p&1) ans*=x, ans%=mod; x*=x; x%=mod; p>>=1; } return int(ans); } vector hashvalues; vector pows; vector invpows; StringHash ohash; StringHash(const vector &s) : ohash(s){ int n = s.size(); hashvalues.resize(n+1); pows.resize(n+1); invpows.resize(n+1); pows[0] = 1; for(int i=1;i<=n;i++){ pows[i] = ll(AL + 1) * pows[i-1] % mod; } invpows[n] = modpow(pows[n], mod-2); for(int i=n-1;i>=0;--i){ invpows[i] = ll(AL + 1) * invpows[i+1] % mod; } for(int i=1;i<=n;i++){ hashvalues[i] = (ll(AL + 1) * hashvalues[i-1] + (s[i-1])) % mod; } // cout<"<= 0 ? ans : ans+mod; } pll gib(ll l,ll r){ return {hashval(l,r),ohash.hashval(l,r)}; } pll merge(pll a,pll b){ pll t=gib(a.first,a.second); pll q=gib(b.first,b.second); ll len=b.second-b.first+1; return { (t.first*pows[len]+q.first)%mod1,(t.second*pp[len]+q.second)%mod2}; } bool compare(int l1,int r1, int l2,int r2){ return hashval(l1,r1) == hashval(l2, r2) && ohash.compare(l1,r1,l2,r2); } }; pll get(StringHash&s,ll ind,ll k){ if(k&s){ if(a==b){return 0;} if(get(s,a,n-2)==get(s,b,n-2)){return 0;} ll lo=0,hi=n-2,ans=hi; while (lo<=hi) { ll mid=(lo+hi)>>1; if(get(s,a,mid)!=get(s,b,mid)){ans=mid; hi=mid-1;} else{lo=mid+1;} } return okgib(a,ans)& nums,int l, int r, int m,StringHash&s){ int n=nums.size(); vector ans(r-l+1); int i=l,j=m+1,k=0; while(i<=m && j<=r){ if(comp(nums[i],nums[j],s)){ ans[k++]=nums[i++]; } else{ ans[k++]=nums[j++]; } } while(i<=m){ ans[k++]=nums[i++]; } while(j<=r){ ans[k++]=nums[j++]; } for(int i=0;i<=r-l;i++){ nums[l+i]=ans[i]; } } void mergesort(vector& nums,int l,int r,StringHash&s){ if(l>=r){ return ; } int m=l+(r-l)/2; mergesort(nums,l,m,s); mergesort(nums,m+1,r,s); merge(nums,l,r,m,s); } vector sortArray(vector& nums) { int n=nums.size(); auto s=StringHash(v); // cout<>t; while (t--){ solve(); } return 0; } void solve(){ ll n,k; cin>>n>>k; k--; vectorv(n); cin>>v; ::v=v; ::n=n; vectorp; for(ll i(0);i