假设两个字符串 $$$s$$$ 和 $$$t$$$ 押韵,如果两个字符串的长度至少为 $$$k$$$,并且它们最后的 $$$k$$$ 字符相等。例如,如果 $$$k = 3$$$,则字符串 abcd 和 cebcd 押韵,字符串 ab 和 ab 不押韵,字符串 aaaa 和 aaaaa 押韵,字符串 abcd 和 abce 不押韵。
你有 $$$n$$$ 串字符串 $$$(s_i, t_i)$$$,对于你知道的每一对字符串,它们应该押韵还是不应该押韵。
找到 $$$k$$$ 的所有可能的非负整数值,使得必须押韵、押韵和不能押韵、不押韵的对。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串对的数量。
接下来的 $$$n$$$ 行包含对的描述 - 每行一个。第 $$$i$$$ 行包含空格分隔的字符串 $$$s_i$$$ 和 $$$t_i$$$ 以及标记 $$$r_i$$$。字符串非空,由小写拉丁字母组成,每个字符串的长度最多为 $$$2 \cdot 10^5$$$。如果字符串必须押韵,则标记 $$$r_i$$$ 等于 $$$1$$$;如果必须不押韵,则标记 $$$0$$$ 等于 $$$0$$$。
保证对于每个测试用例,至少有一对 $$$r_i$$$ 等于 $$$1$$$,并且所有测试用例的所有字符串的总长度不超过 $$$4 \cdot 10^5$$$。
输出
对于每个测试用例,首先打印整数 $$$m$$$ — $$$k$$$ 的可能非负整数值的数量,使得必须押韵、押韵和必须不押韵、不押韵的对。接下来,打印 $$$k$$$ 的所有这些值(不重复)。您可以按任何顺序打印它们。
示例
输入 #1
3 1 kotlin heroes 1 2 join kotlin 1 episode eight 0 4 abc abcdef 0 xyz zzz 1 aaa bba 0 c d 0
输出 #1
1 0 2 1 2 0
注意
在第一个测试用例中,如果 $$$k$$$ 至少为 $$$1$$$,则 kotlin 和 Heroes 不押韵。
在第二个测试用例中,对于 $$$k = 2$$$ 连接和 kotlin 押韵,而 Episode 和 8 不押韵。