#23022. 新年灯火

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

「新年的钟声即将敲响,让我们怀着对未来的美好向往,共同迎接新年的第一缕阳光。
祝愿祖国繁荣昌盛、国泰民安!祝愿世界和平美好、幸福安宁!祝愿大家新年快乐、皆得所愿!」
——改自《二〇二三年新年贺词》

2023 年最后一天的夜晚,Bardisk 从窗台向外望去。点点繁星销声匿迹,万家灯火映入眼帘。如此一片安宁祥和之中,Bardisk 默默期许着明年能够得偿所愿。

作为一个学计算机的人,Bardisk 不甘心用普通的方式许愿。他竖起一排灯泡,其中每个灯泡都可以调多档强度。然后,他想要用码分多址的方式来利用灯泡来表示他的多个愿望。这个码分多址的过程可以描述为,假设灯泡、愿望各有 个( 是 的次幂),每个愿望以 01 序列表示且长度为 ,则利用一个大小为 的对称且具有正交性质的矩阵(相同行向量点积相等且为 ,不同行向量点积为零,且仅由 两种元素构成)对长度为 的愿望矩阵进行变换而得到一个 的矩阵,变换后矩阵的第 列表示灯泡第 个时刻的亮度。

具体地,我们用类似沃尔什变换的方法来构造这个对称类正交矩阵。

令 表示 的变换矩阵,则 。

对于 ,。

现在给你愿望矩阵,请输出最终变换后的矩阵。

输入格式

第一行 个正整数,。

接下来 行,每行为一个长度 的 01 字符串,表示愿望的 01 序列。

输出格式

输出共 行,每行为一个长度为 的整数序列,使用空格隔开。表示本题的答案。

样例

输入样例1

4 3
100
000
000
010

输出样例1

1 1 0 
1 -1 0 
1 -1 0 
1 1 0 

输入样例2

2 5
01000
11111

输出样例2

1 2 1 1 1 
-1 0 -1 -1 -1 

数据范围与提示

本题是期末机试的备选 T1/T2 之一。

对于所有测试数据,。