时风正在安排一次会议。会议厅有$$$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$$$第列。