#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N=1e5+5, mod = 1e9+7, inf = 1e18, p = 131;

int n, m, q, k;
int hsha[305][60005], hshb[305][60005], pw[60010];
string s;
bool b;

int geta(int idx, int l, int r) {
    return hsha[idx][r]-hsha[idx][l-1]*pw[r-l+1];
}

int getb(int idx,int l,int r) {
    return hshb[idx][r]-hshb[idx][l-1]*pw[r-l+1];
}

int solve(int idxa,int idxb, int l, int r, int cnt) {
    if(l==r) return 1;
    int mid = (l+r)>>1;
    int tla = geta(idxa, l, mid), tra = geta(idxa, mid+1, r);
    int tlb = getb(idxb, l, mid), trb = getb(idxb, mid+1, r);
    if(b) return 100;
    if(tla!=tlb) cnt += solve(idxa, idxb, l, mid, 0);
    if(cnt>k) b=1;
    if(b)return 100;
    if(tra!=trb) cnt += solve(idxa, idxb, mid+1, r, 0);
    return cnt; 
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q >> m >> k;
    pw[0] = 1; for (int i=1; i<=m; i++) pw[i] = pw[i-1]*p;
    for (int i=1; i<=n; i++) {
        cin >> s; s = "#"+s;
        for (int j=1; j<=m; j++) hsha[i][j] = hsha[i][j-1]*p + (int)s[j];
    }
    for (int i=1; i<=q; i++) {
        cin >> s; s = "#"+s;
        for (int j=1; j<=m; j++) hshb[i][j] = hshb[i][j-1]*p + (int)s[j];
    }
    for (int i=1; i<=q; i++) {
        int ans = 0;
        for (int j=1; j<=n; j++) {
            b = 0;
            int t = solve(j, i, 1, m, 0);
            if(t<=k) ans++;
        }
        cout << ans << '\n';
    }
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:3:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::__cxx11::basic_string<char>::_Alloc_hider::~_Alloc_hider()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = char]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/string:54:
/usr/include/c++/13/bits/basic_string.h:181:14: note: called from here
  181 |       struct _Alloc_hider : allocator_type // TODO check __is_final
      |              ^~~~~~~~~~~~