assert(2<=len(input)<=10**5)