Задача о динамическом программировании
В этой задаче вам предстоит решить простое линейное уравнение с одной переменной 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, если у уравнения нет решения или если существует бесконечно много решений соответственно. Обратите внимание, что вывод чувствителен к регистру.