he input consists of many lines. Each line is a string S with length <= 1000000. The string S does not contain any spaces.