GitHub 源文件 Markdown 中文

Magic Bread

• Indicative time limit: 1.0 s (environment and measurements).
• Deployment time limit: measure the reference program in the target environment, multiply the slowest case's median time by 2, and round up to the next 0.5 seconds.
• Memory limit: 512 MB.

Story

The farm grows two kinds of magical wheat, called Five Hues and Six Colors, represented by \(0\) and \(1\) . The fields form a ring, with an automatic crafting unit beside each field.

The machine divides its wheat sequence into blocks of a fixed length. It works only when every block is a palindrome and all blocks are identical. The farmer will walk at most one lap and wants the longest usable segment with each field as an endpoint.

Formal Problem Statement

You are given a binary string \(s\) of length \(n\) . Positions \(1,\ldots,n\) form a ring in that order.

For every position \(i\) and level \(j\) with \(1\le j\le K\) , consider a nonempty consecutive ring segment having \(i\) as either endpoint. You may start at \(i\) and traverse in either direction. Its length must not exceed \(n\) , and no position may be used twice.

A sequence of length \(\ell\) can make level-\(j\) bread if and only if \(j\) divides \(\ell\) and, when divided into consecutive blocks of \(j\) characters starting at the chosen endpoint, every block is identical and is a palindrome. A palindrome reads the same forward and backward.

Let \(a_{i,j}\) be the largest possible length, or \(0\) if none exists. For each \(i\) , output

\[ X_i=\bigoplus_{j=1}^{K}\bigl(j\cdot a_{i,j}\bigr) \]

Here \(\oplus\) denotes bitwise XOR. Compute the products before applying XOR.

Input Format

The first line contains \(n,K\) .

The second line contains a string \(s\) of length \(n\) , consisting only of 0 and 1 .

Output Format

Print \(n\) lines. Line \(i\) contains the integer \(X_i\) .

Sample 1

Input

5 5
10101

Output

22
24
8
24
22

Sample 2

Input

6 6
110011

Output

42
21
34
34
21
42

Sample 3

Input

1 20
0

Output

1

Sample Explanation

In sample 1, the five lengths for position \(1\) are \((2,2,3,0,5)\) , giving \(X_1=2\oplus4\oplus9\oplus0\oplus25=22\) . A length-\(2\) segment can go backward from position \(1\) to position \(5\) , producing 11 .

Numbers label positions, and the boxes beneath them show wheat types. The arrow illustrates selecting the segment from position \(1\) toward position \(5\) .

In sample 2, the six lengths for position \(2\) are \((4,4,3,4,0,0)\) ; multiplying by their levels and XORing gives \(21\) . In sample 3, only level \(1\) is possible.

Constraints and Guarantees

For all test cases: \(1\le n\le1000000\) and \(1\le K\le20\) . It is possible that \(K>n\) ; every \(a_{i,j}\) with \(j>n\) is then \(0\) .

Score	Additional restrictions
100%	None