xs = [0] * (10 ** 9)