Description

给出一个只包含 0 和 1 的字符串（长度在 1 到 1000 之间），求其每一个非空子串出现的次数。

子串：字符串中任意个连续字符组成的子序列称为该字符串的子串。

Input

一行，一个 01 字符串。

Output

对所有出现次数在 1 次以上的非空子串，输出该子串及出现次数，中间用单个空格隔开。按子串的字典序从小到大依次输出，每行一个。

Samples

10101

0 2
01 2
1 3
10 2
101 2