Проблема динамічного програмування
У цій задачі вам потрібно розв'язати дуже просте лінійне рівняння з однією змінною x без дужок! Приклад такого рівняння виглядає наступним чином:
2x – 4 + 5x + 300 = 98x
Вираз у загальній формі міститиме символ '=' з двома виразами по обидва боки. Кожен вираз складається з одного або більше членів, об'єднаних операторами '+' або '-'. У виразах не допускаються унарні оператори плюс або мінус. Кожен член є або одним цілим числом, або цілим числом, за яким слідує малий символ x, або одиничний символ x, що еквівалентно 1x.
Ви повинні написати програму, щоб знайти значення x, яке задовольняє рівняння. Зверніть увагу, що рівняння може не мати розв'язку або мати нескінченно багато. Ваша програма повинна виявляти ці випадки також.
Вхідні дані
Перше число у вхідному рядку, t (1 ≤ t ≤ 10) — це кількість тестових випадків, за яким слідують t рядків довжиною не більше 255 кожен, що містять рівняння. У рівняннях немає пробілів, а змінна завжди представлена малим символом x. Коефіцієнти є цілими числами в діапазоні (0…1000) включно.
Вихідні дані
Вихід містить один рядок на кожен тестовий випадок, що містить розв'язок рівняння. Якщо s є розв'язком рівняння, вихідний рядок повинен містити s (цілу частину s, тобто найбільше ціле число, менше або рівне s). Вихід повинен бути IMPOSSIBLE або IDENTITY, якщо рівняння не має розв'язку або має нескінченно багато розв'язків, відповідно. Зверніть увагу, що вихід чутливий до регістру.