Щаслива підпослідовність

Обмеження: 2 сек., 256 МіБ

Марічка та Зеник люблять щасливі підпослідовності.

Рядок $x$ називається підпослідовністю рядка $y$, якщо з $y$ можна видалити деяку кількість елементів (можливо, нульову), щоб залишився рядок $x$.

Найдовшою спільною підпослідовністю рядків $x$ та $y$ є такий найдовший рядок $z$, що є одночасно підпослідовністю $x$ та підпослідовністю $y$.

У Марічки є рядок $s$ довжини $n$, який складається з малих латинських букв. Зеник хоче собі рядок $t$ також довжини $n$, який складається з малих латинських букв, такий, що довжина найдовшої спільної підпослідовності $s$ i $t$ рівна 47.

Допоможіть Зенику знайти такий рядок.

Вхідні дані

Вхідні дані містять єдиний рядок $s$.

Вихідні дані

Виведіть єдиний рядок $t$ довжини $n$.

Обмеження

$47 \le n \le 10^3$.

algotesteristhegreatestprogrammingplatformonearthhappyluckyday

xaxlxgxoxtxexsxtxexrxishgeatstroramindpatfrgnehthjappyluckyday

Приклади