对于一个给定的二进制串 s（即仅由字符 0 和 1 组成的串），其评分是这样计算的：将原串切分为若干段，使得每段包含的字符是一样的，且相邻两段包含的字符是不一样的。该字符串的评分定义为各段长度的异或值（如果只有一段，评分就是这段的长度）。

异或（Exclusive OR，简称 XOR）是一种数学运算符，用于计算机中的位运算。当且仅当两个输入值不同时，异或运算输出为真（1），否则输出为假（0）。

例如，串 "10001100001" 可以切分为 5 段，即 "1"、"000"、"11"、"0000"、"1"，其评分就是 1 ^ 3 ^ 2 ^ 4 ^ 1 = 5。

假设每一步我们可以交换 2 个相邻的字符，并且可以这样执行任意多步（当然也可以执行 0 步）。对每个可能的评分 x，你能得到多少个不同的串？将原串 s 通过交换操作变成评分为 x 的串，所用的最少步骤是多少次？

输入格式

输入在一行中给出非空的原始二进制串 s，其长度不超过 64。

输出格式

对每个可能的评分，在一行中输出 3 个空格分隔的整数，依次为：评分值、对 s 执行任意多步交换后能得到的不同串的个数、将 s 通过交换操作变成该评分的串所需要的最少步骤数。 按评分的升序输出。

输入样例

010

输出样例

1 1 0
3 2 1

限制

时间限制：1000，内存限制：65536