The Winter holiday will be here soon. Mr. Chanek wants to decorate his house's wall with ornaments. The wall can be represented as a binary string a of length n. His favorite nephew has another binary string b of length m (m ≤ n).

Mr. Chanek's nephew loves the non-negative integer k. His nephew wants exactly k occurrences of b as substrings in a. 

However, Mr. Chanek does not know the value of k. So, for each k (0 ≤ k ≤ n - m + 1), find the minimum number of elements in a that have to be changed such that there are exactly k occurrences of b in a.

A string s occurs exactly k times in t if there are exactly k different pairs (p,q) such that we can obtain s by deleting p characters from the beginning and q characters from the end of t.

Input

The first line contains two integers n and m (1 ≤ m ≤ n ≤ 500) — size of the binary string a and b respectively.

The second line contains a binary string a of length n.

The third line contains a binary string b of length m.

Output

Output n - m + 2 integers — the (k+1)-th integer denotes the minimal number of elements in a that have to be changed so there are exactly k occurrences of b as a substring in a.

Example

Input


9 3
100101011
101


Output


1 1 0 1 6 -1 -1 -1

Note

For k = 0, to make the string a have no occurrence of 101, you can do one character change as follows.

100101011 → 100100011

For k = 1, you can also change a single character.

100101011 → 100001011

For k = 2, no changes are needed.
// Don't place your source in a package


import javax.swing.*;
import java.lang.reflect.Array;
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
import java.util.stream.Stream;



// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

        long Long() {
            return Long.parseLong(next());
        }

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        //reading /writing file
        //Scanner sc=new Scanner(new File("src/text.txt"));
        //PrintWriter pr=new PrintWriter("output.txt");
        //File file = new File("src/text.txt");

        int T=1;
        for(int t=0;t<T;t++){
            Solution sol1=new Solution(out,fs);
            sol1.solution();
        }
        out.flush();

    }


    public static int[] Arr(int n){
        int A[]=new int[n];
        for(int i=0;i<n;i++)A[i]=Int();
        return A;
    }
    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}








class Solution {
    PrintWriter out;
    int INF = 10000000;
    int MOD = 998244353 ;
    long mod = 1000000007;
    Main.FastScanner fs;
    public Solution(PrintWriter out,Main.FastScanner fs) {
        this.out = out;
        this.fs=fs;
    }


    int dp[][][];
    int pre[];
    int change[];
    public void solution() {
        int n =fs.Int();
        int m =fs.Int();
        String s = fs.Str();
        String t = fs.Str();
        char A[]=s.toCharArray();
        char B[]=t.toCharArray();
        pre=pre(t);
        change=new int[pre.length];

        dp = new int[n][m][n - m + 2 + 1];
        for(int i = 0; i < dp.length;i++){
            for(int j = 0; j < dp[0].length;j++){
                Arrays.fill(dp[i][j],-1);
            }
        }

        //pre-processing
        for(int i = 0; i < change.length;i++){
            char c = B[i];
            char d = c;
            if(c=='0')d='1';
            else d = '0';

            int cur = i;
            while(cur!=0){
                if(B[cur] == d){
                    change[i]=cur;
                    break;
                }
                cur=pre[cur-1];
            }

        }

        //System.out.println(Arrays.toString(pre));
        //System.out.println(Arrays.toString(change));


        for(int k = 0; k < n - m + 2; k++){
            int res = dfs(A,B,0,0,k);
            if(res>n){
                out.print(-1+" ");
            }
            else{
                out.print(res+" ");
            }
        }

    }

    public int dfs(char A[],char B[],int i,int j,int k){
        if(i >= A.length){
            if(k!=0)return 1000000;
            return 0;
        }
        if(dp[i][j][k]!=-1){
            return dp[i][j][k];
        }



        int res = 1000000;
        if(A[i]==B[j]){
            if(j==B.length-1){//at the end
                if(k==0){
                    if(j!=0 && change[j - 1] != -1){
                        res=Math.min(res,1 + dfs(A,B,i+1,change[j - 1],k));
                    }else{
                        return 1000000;
                    }
                }
                else{
                    res =Math.min(res,dfs(A,B,i+1,pre[j],k-1));
                }
            }
            else{
                res = Math.min(res,dfs(A,B,i+1,j+1,k));

                //change to
                if(j!=0 && change[j - 1] != -1){
                    res=Math.min(res,1 + dfs(A,B,i+1,change[j - 1],k));
                }


            }
        }
        else{//not same
            if(j!=0){
                if(j==B.length-1){
                    if(k!=0)res = Math.min(res,1 + dfs(A,B,i+1,pre[j],k-1));
                }
                else{
                    res = Math.min(res,1 + dfs(A,B,i+1,j+1,k));
                }
                res=Math.min(res,dfs(A,B,i,pre[j - 1],k));
            }
            else{
                if(j==B.length-1){
                    if(k!=0)res = Math.min(res,1 + dfs(A,B,i+1,0,k-1));
                }
                else{
                    res = Math.min(res,1 + dfs(A,B,i+1,j+1,k));
                }


                res = Math.min(res,dfs(A,B,i+1,j,k));//just skip
            }
        }

        dp[i][j][k]=res;
        return res;
    }

    public int[] pre(String pattern){
        int pre[]=new int[pattern.length()];
        int l=0,r=1;
        while(r<pattern.length()){
            if(pattern.charAt(r)==pattern.charAt(l)){
                pre[r]=l+1;
                l++;
                r++;
            }else{
                if(l==0)r++;
                else{
                    l=pre[l-1];
                }
            }
        }
        return pre;
    }

}





