← 返回题目列表

Codeforces · 1677/B

B. 时风和会议

中文机器翻译题面 查看原题

时风正在安排一次会议。会议厅有$$$n$$$行和$$$m$$$列座位。

参加会议的学生正好有$$$n \cdot m$$$ 个,包括几个调皮的学生和几个认真的学生。学生的编号从 $$$1$$$ 到 $$$n\cdot m$$$。同学们按顺序进入会议室。当第 $$$i$$$-th 学生进入会议厅时,他将坐在第 $$$1$$$-st 排的第 $$$1$$$-st 列,已经就座的学生将后退一个座位。具体来说,坐在第 $$$i$$$ 行第 $$$j$$$ ($$$1\leq j \leq m-1$$$) 列的学生将移动到第 $$$i$$$ 行的第 $$$(j+1)$$$ 列,坐在第 $$$i$$$ 行第 $$$m$$$ 列的学生将移动到第 $$$i$$$ 行的第 $$$(j+1)$$$ 列。 $$$(i+1)$$$第$$$1$$$第列。

例如,有一个会议厅,有$$$2$$$行和$$$2$$$列座位,如下所示:

将有$$$4$$$学生按顺序进入会议室,表示为二进制字符串“1100”,其中“0”代表顽皮的学生,“1”代表认真的学生。会议厅座位变动如下:

当且仅当该行或该列中至少有一个认真的学生时,才表示该行或该列良好。请预测第 $$$i$$$ 名学生进入会议厅后,对于所有 $$$i$$$ 来说,好的行数和列数。

输入

第一个包含一个正整数 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — 测试用例的数量。

对于每个测试用例,第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1 \leq n,m \leq 10^6$$$; $$$1 \leq n \cdot m \leq 10^6$$$),表示会议厅有 $$$n$$$ 行和 $$$m$$$ 列座位。

第二行包含一个二进制字符串 $$$s$$$,长度为 $$$n \cdot m$$$,仅由零和一组成。如果$$$s_i$$$等于'0'代表第$$$i$$$个学生是顽皮的学生,$$$s_i$$$等于'1'代表第$$$i$$$个学生是认真的学生。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,打印一行,其中包含 $$$n \cdot m$$$ 整数 - 第 $$$i$$$ 个学生进入会议室后的良好行数和列数。

示例

输入 #1

3
2 2
1100
4 2
11001101
2 4
11001101

输出 #1

2 3 4 3
2 3 4 3 5 4 6 5
2 3 3 3 4 4 4 5

注意

第一个测试用例如语句中所示。

$$$1$$$-st学生进入会议室后,有$$$2$$$好的行和列:$$$1$$$-st行和$$$1$$$-st列。

第$$$2$$$-nd学生进入会议室后,有$$$3$$$好行和列:$$$1$$$-st行,$$$1$$$-st列和$$$2$$$-nd列。

$$$3$$$-rd学生进入会议室后,$$$4$$$行列均正常。

第$$$4$$$个学生进入会议室后,有$$$3$$$个好的行和列:第$$$2$$$第行、第$$$1$$$第列和第$$$2$$$第列。