定义“均匀树”（Uniform tree）为一种在给定层级（即距离根节点的距离）上的所有节点都具有相同度数（即子节点数量）的树。由于同一层级的所有节点都有相同数量的子节点，因此均匀树可以简单地表示为一个整数列表，用以指示每一层级的子节点数量。例如，列表 [2 3 5 0] 表示一棵树，其根节点有 2 个子节点，根节点的每个子节点有 3 个子节点，每个孙子节点有 5 个子节点，而每个曾孙节点没有子节点，因此是叶子节点。

在本题中，我们将“子树”（Subtree）重新定义为包含树根的连通子图。这与通常的子树定义略有不同。

给定一棵树的描述，找出该树中所有唯一的均匀子树。例如，下图展示了一棵树及其所有唯一的均匀子树：

输入格式

输入包含多个测试用例。每个测试用例由单行上的单个字符串组成，表示一棵树。该字符串是一系列匹配的圆括号。每一对匹配的圆括号代表一个节点，括号之间的内容表示其子节点。树中的节点数不超过 4,000 个。字符串中不会包含空格或其他任何字符。输入以一行单个 0 结束。

输出格式

对于每个测试用例，输出该给定树的所有唯一均匀子树，每个子树（即一个列表）占一行。整数之间打印一个空格，其他任何地方均不打印空格。不要在列表之间或测试用例之间打印任何空行。对于给定的测试用例，请按第一个元素、然后是第二个元素、第三个元素等顺序对列表进行排序。

样例

样例输入 1

(((()))(()(()())()))
(())
0

样例输出 1

0
1 0
1 1 0
1 1 1 0
1 1 2 0
1 2 0
1 3 0
2 0
2 1 0
2 1 1 0
0
1 0

说明

第一个样例输入和输出对应于图中所示的树及其子树。