P17778 锦木千束不是罪过

『心臓が逃げる！』

千束和泷奈厌倦了石头剪刀布，所以她们打算设计一个新的手势游戏。该游戏可以形式化如下： 一个游戏可以描述为一个 $n$ 个点的竞赛图，每个点都有一个颜色，点 $i$ 的颜色为 $c_i$，颜色共 $m$ 种，编号从 $1$ 至 $m$，保证每个颜色均有至少一个节点。 泷奈会首先选择一个颜色，记作 $p$。她的策略是等概率随机地选择颜色为 $p$ 的某一个点。千束知道泷奈的策略（包括选定颜色和随机出招策略，但不知道具体选择哪一个点），她会选择胜率最大的一个点。 如果点 $i$ 在竞赛图上指向点 $j$，那么选 $i$ 的人就战胜了选 $j$ 的人。特殊地，若二人选择了同一个点，视作泷奈胜利。 现在给定 $n,m$ 与所有点的颜色，泷奈请你给所有边定向，并帮她选择 $p$，以最大化泷奈的胜率。 注：某人的胜率定义为，在泷奈选好颜色、千束按上述规则选好点后，泷奈可以选择的点中，选了之后能使此人获胜的点数，与泷奈可以选择的总点数之比。

第一行输入两个正整数 $n,m$。 第二行输入 $n$ 个正整数，第 $i$ 个数为 $c_i$。

第一行输出两个整数 $a,b$，分别表示你构造的方案下千束选点之后，泷奈可以选择的点中选了能使自己获胜的点数，与泷奈可以选择的总点数。 对于第二行至第 $n$ 行，第 $i$ 行输出 $i-1$ 个 $0$ 或 $1$，以空格隔开，其中第 $j$ 个数为 $1$ 表示点 $i$ 战胜点 $j$，否则表示点 $j$ 战胜点 $i$。 第 $n+1$ 行输出 $p$ 即泷奈选择的颜色。 若存在多种符合条件的构造方案，输出任意一种均可。

#### 【数据范围】 对所有数据，满足 $1\le m\le n\le 5000$，$1\le c_i\le m$。 #### 【样例解释】 ##### 样例 #1  在设计的局面下，泷奈只能选点 $2$，无论千束选择哪一个点，她都会必然会落败，故泷奈的胜率是 $100\%$。 泷奈可以获胜的点数为 $1$，她可以选择的点总数为 $1$，故输出 `1 1`。 显然不存在更大的胜率。 ##### 样例 #2  在设计的局面下，泷奈可能会选点 $1,2$，千束只有在选择点 $2$ 时必然会落败，选其余任意点千束都会有 $50\%$ 的胜率，故而千束将会选择点 $2$ 以外的任何点，泷奈的胜率为 $50\%$。 泷奈可以获胜的点数为 $1$，她可以出的点总数为 $2$，故输出 `1 2`。 可以证明无法构造出更大的胜率。 --- *去做最想做的事情吧。*