34775번 - Generating patterns 다국어

문제

Sandy is developing a new computer as part of the ambitious System for Binary Compression (SBC) project. This project is part of a major technological challenge known as the Interface for Compact Pattern Coding (ICPC), whose goal is to achieve maximum efficiency in writing large volumes of data.

The SBC proposal is bold: choose a base pattern $B,ドル consisting of 8ドル$ bits $b_0, \dots , b_7,ドル and from it generate any other pattern by applying only simple, fast operations.

Sandy wants to write a sequence of $N$ bits to memory, with $N ≥ 8,ドル denoted by $C = c_0, \dots , c_{N−1}$. Initially, memory contains only zeros. She may then repeat the following operation any number of times:

• Choose an integer $i$ between $−7$ and $N − 1,ドル the position at which $B$ will be applied;
• For each position of $B$ that overlaps the sequence, that is, for every $j$ from 0ドル$ to 7ドル$ such that 0ドル ≤ i + j ≤ N − 1,ドル replace $c_{i+j}$ with $b_j ⊕ c_{i+j},ドル where $⊕$ denotes the XOR (exclusive OR) operation.

The following example illustrates two applications of the procedure: applying pattern $B$ to content $C,ドル the final result $C′$ is obtained.

Since the data we want to write to memory is usually not random, Sandy believes that, with a good choice of base pattern $B,ドル it will be possible to produce the desired content with few operations.

To test this hypothesis, she needs your help: given the content $C$ that must be written to memory, determine the base pattern $B$ that minimizes the number of operations needed to generate $C$ as described, and also the number $Q$ of operations required.

It can be proven that it is always possible to write any content using this procedure. However, for the SBC project to be successful and earn the ICPC seal of excellence, your solution needs to be fast and efficient!

입력

The first line contains an integer $N$ (8ドル ≤ N ≤ 4096$), the length of $C$.

The second line contains a sequence of $N$ bits, representing $C,ドル the content that must be written to memory.

출력

Your program should print a single line containing the 8ドル$-bit sequence $B,ドル representing the base pattern that minimizes the number of operations, and an integer $Q,ドル representing the minimum number of operations.

If there is more than one pattern $B$ that minimizes the number of operations, print the one with the smallest integer value when interpreted in base 2ドル,ドル where $b_0$ is the most significant bit and $b_7$ is the least significant bit.

제한

노트