题目描述

I never said “640K should be enough for anybody! ”. —— Bill Gates

阿米巴是小强的好朋友。他经常和小强通过即时通讯工具聊天。但是，小强还是喜欢和阿米巴面对面的在一起的感觉，于是他想说服阿米巴放弃即时通讯工具。小强提出的一个理由是，别人可能偷看到他们两个人之间的相互说的“那些话”从而造出“大新闻”。

阿米巴认为他们可以通过加密聊天来解决这个问题。小强和阿米巴都知道，只有一次一密这种真正安全的加密算法才能保护住他们的信息。这种加密方法虽然很安全，但是需要在事前约定很长的一个随机串。

于是，小强又提出，他的 u 盘太小，根本存不下太多东西，一次无法从阿米巴那里拷贝足够长的随机串。为了减少事前约定的串的长度，阿米巴提出了一个“随机倍增器”。这个“随机倍增器”可以将一个 $n$ 位的随机串变成一个 $2\times n$ 位的看起来也很随机的串。

具体的，对于一个长度为 $n$ 的 $01$ 串，选取参数 $m$，$c$，阿米巴用下面的方法把它变成一个长度为 $2n$ 的串：

首先，令 $h$ 为 $1371\operatorname{mod} 2^m$，$s=0$。

对于每个 $i$ 从 $1$ 到 $n$，设输入的第 $i$ 位是 $x_i$，做下面几个事情：

$s=\operatorname{RotL}(3432918353\times s+c\operatorname{mod} 2^{32},32)\times 461845907\operatorname{mod} 2^{32}$；

$h=h\oplus(s\operatorname{mod} 2^m\oplus x_i)$；

$h=\operatorname{RotL}(h,m)$；

$h=(h\times 5+3864292196)\operatorname{mod} 2^m$。

输出 $h$ 的二进制位从低到高的第 $m$ 位、第 $m-1$ 位（例如，如果 $h=13$（二进制是 $1101$），$m=4$，那么就是 $1$ 和 $1$）。

在这里，$\operatorname{mod}$ 表示取模，即，$a\mod b$ 为一个 $0-(b-1)$ 之间的整数，表示 $a$ 模 $b$ 的余数。$\operatorname{RotL}(a,b)$表示从一次 $b$ 位的循环左移，即，将 $a$ 的所有二进制位向更高位移动一位，原来的第 $b$ 位移动回第 $1$ 位（比如，$\operatorname{RotL}(13,4)=11$，因为 $13$ 的二进制是 $1101$，循环左移变成 $1011$，就是 $11$）。

小强从这个算法的常数中一下就看出了这个算法改造自著名的 murmurHash3。不过，小强认为阿米巴连 NOIP 都没有考过，他改造出来的算法一定是有缺陷的。阿米巴偏偏不信这点。

为了向阿米巴说明这个算法的“随机性”不是特别强，小强想精心构造一个输入串，使得输出串中 $0$ 的个数特别多。我们知道，如果这个算法真的很随机，因为输入只有 $n$ 位，所以输出中应该是不会有太多的 $0$ 的。曾经获得过 NOIP 普及组二等奖的小强还是有一定的算法能力的，他很快就想出了一个构造的算法。但是，问题在于小强没有带笔记本，他只能用自己的手机上的浏览器运行 javascript 来进行计算。但是手机上的内存非常紧张，需要用的数组根本存不下！

为了小强和阿米巴在一起的美好时光，你要利用非常紧缺的内存来完成输入串的构造。

输入格式

输入一行，$n$，$m$，$c$。

输出格式

第一行一个整数，表示输出串中 $1$ 的个数的最小值。

然后，输出一行 $n$ 个 $01$，表示输入串。如果有多种可能的输入，你可以任选一个。

3 3 5

0
101

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 5\times 10^3$，$3\le m\le 20$，$n\times 2^m\le 5\times 10^7$，$0\le C<2^{31}$。

题目来源

By 佚名提供