说明

给你一个 $n \times m$ 的网格，你需要在网格上放置若干个国际象棋中的王，使得每个王的攻击范围内有且仅有 $k$ 个王。

你需要构造使得你放置王的数量 $\ge z$，给出任意一种方案即可。

注：国际象棋中的王的攻击范围为距离它切比雪夫距离为 $1$ 的格子。

输入格式

输入只有一行，输入四个整数 $n,m,k,z$。

输出格式

第一行你需要输出一个数代表你构造的方案王的个数。

你需要输出一个 $n \times m$ 的 $01$ 方阵，代表你构造的网格，$0$ 代表此处不放置王，$1$ 代表此处放置王。

请保证你构造的网格符合题目限制，否则你将会得到 $0$ 分。

3 3 3 0

4
011
011
000

提示

【数据范围】

本题只有两个测试点：

• 测试点 1（20 pts）：$k=2$，$n=m=1003$，$z=5\times10^5$。
• 测试点 2（55 pts）：$k=3$，$n=1003$，$m=1004$，$z=5\times10^5$。

记你输出的方案王的个数为 $y$，你将会得到此测试点 $\min(100,\left \lfloor \frac{-10^6}{y-z-10^4} \right \rfloor)\%$ 的分数。