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

Limits: 2 sec., 256 MiB

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

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

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

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

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

Input

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

Output

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

Constraints

\(47 \le n \le 10^3\).

algotesteristhegreatestprogrammingplatformonearthhappyluckyday

xaxlxgxoxtxexsxtxexrxishgeatstroramindpatfrgnehthjappyluckyday

Приклади