Extended Multi Members (Python)Разреженные Многочлены(Python)

Напишите программу сложения, умножения и деления с остатком от разреженных многочленов, т.е. многочленов, для которых мы храним только ненулевые члены.

Разреженный многочлен определяется как последовательность пар (e,x)(e,x), где ee — показатель степени, а xx — соответствующий коэффициент. Пары перечислены в порядке убывания показателей, каждая на отдельной строке. Весь полином заканчивается линией -1 -1. Мы никогда не перечисляем пары с нулевыми коэффициентами, особенно нулевой полином представлен самой линией -1 -1.

Например полином 3x^5 - x^2 + 7 запишем так:

5 3

2 -1

0 7

-1 -1

Первая строка ввода говорит нам, какую операцию выполнять: add для сложения, mul для умножения или div для деления с остатком. В следующих строках вводятся два разреженных полинома.

Снова запишите результат операции в виде разреженного многочлена. Результатом операции div являются два многочлена: частное и остаток от деления. Обратите внимание, что при делении могут получиться нечетные числа; запишите их в виде дробей (мы рекомендуем использовать тип Fraction).

Например сложение Input:

add

6 1

4 3

3 -3

0 5

-1 -1

3 3

0 -3

-1 -1

Правильный Output:

6 1

4 3

0 2

-1 -1

Если бы операция была  mul Output:

9 3

7 9

6 -12

4 -9

3 24

0 -15

-1 -1

И про деление div Output:

3 1/3

1 1

0 -2/3

-1 -1

1 3

0 3

-1 -1

Примечание: функции NumPy для работы с полиномами не подходят для этой задачи, так как не используют разреженное представление полиномов. Поэтому они слишком медленны для полиномов высокой степени с большим количеством нулевых членов.