Ваша задача — для каждого префикса строки проверить, можно ли его разбить на 1, 2, 3, 4, 5, …, 31 непустой палиндром.

На вход подаётся строка из n строчных латинских букв (1 ≤ n ≤ 300 000).

Выведите n целых неотрицательных чисел, разделяя их переводами строк. В i-й (1 ≤ i ≤ n) строке требуется выдать число-маску, в которой (j − 1)-й бит равен единице, если префикс строки длины i можно разбить на j палиндромов.

1₁₀ = 1₂; 2₁₀ = 10₂; 5₁₀ = 101₂; 14₁₀ = 1110₂; abaa = aba|a = a|b|aa = a|b|a|a.