Рівняння#3150

Рівняння

1 секунда

256 мегабайтів

Легка

Програміста Вову вже давно цікавлять різноманітні задачі на рядки. У цій задачі рядком називається будь-яка послідовність символів ASCII з кодами від $33$ до $126$ .

Нещодавно Вова дізнався про операції над рядками:

Додавання рядків, яке позначається символом " $+$ ". Наприклад, Doctor+Who=DoctorWho.
Множення рядків, яке позначається символом " $*$ ". Якщо $S = A * B$ S=A*B, то $S = a_{1} + B + a_{2} + B + \dots + a_{n} + B$ S=a_1+B+a_2+B+\ldots+a_n+B, де $a_{i}$ a_i — $i$ -ий символ рядка $A$ (символи рядка нумеруються, починаючи з $1$ ). Наприклад, aca*x=axcxax.

Після цього Вова замислився: чому б не придумати рівняння, невідомим у якому був би рядок? І він почав розв'язувати вигадані ним рівняння.

Перейдемо до формальних визначень. Будемо називати рівнянням послідовність $a_{1} ° a_{2} ° \dots ° a_{n} = b$ a_1°a_2°\ldots°a_n=b, де $a_{i}$ a_i — або невідомий рядок (позначається "?"), або певний заданий непорожній рядок (записується символами цього рядка без додаткових символів чи роздільників), $b$ — заданий непорожній рядок, а символи " $°$ " можуть відповідати або операції додавання, або множення (у різних місцях можуть стояти різні оператори). Усі операції виконуються строго зліва направо; дужки не впливають на порядок виконання операцій. Гарантується, що існує $i$ , для якого $a_{i}$ a_i = "?". Символи "?", " $+$ ", " $*$ " та " $=$ " не використовуються як символи у відомих рядках. Крім того, усі $a_{i}$ a_i та $b$ — непорожні рядки.

Потрібно розв'язати таке рівняння, враховуючи, що непорожній розв'язок існує.

Вхідні дані

Перший рядок містить рядок $S$ , що задає рівняння. Кількість операцій не перевищує $200000$ , а довжина рядка $S$ не перевищує $300000$ символів. Рівняння завжди містить хоча б один символ "?".

Вихідні дані

Виведіть значення невідомого рядка.

Приклади

Приклад 1