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

Обмеження: 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

Приклади