Задача A. Сложение неотрицательных длинных чисел ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
5

8

100000000000000000000
29

100000000000000000029

Задача B. Приведение многочлена ≡

Условие

Пусть имеется многочлен, представленный в следующем виде: C₀ ⋅ (x − C₁) ⋅ …  ⋅ (x − C_n), где все C_i принадлежат кольцу вычетов по некоторому заданному модулю p.

Требуется привести его к каноническому виду: A₀ + A₁ ⋅ x + …  + A_n ⋅ xⁿ.

Формат входного файла

В начале входного файла "input.txt" содержится значение модуля p и натуральное число n. Далее следует набор значений C_i, где i = 0, 1, …, n.

Формат выходного файла

Выходной файл "output.txt" должен содержать массив коэффициентов A_i.

Ограничения

2 ≤ p < 2⁶⁴, 0 ≤ C_i < p, 0 ≤ n ≤ 500

Примеры тестов

100 5
2
13
4
37
6
29

48
68
90
90
22
2

2 4
1
0
1
0
1

0
0
1
0
1

Задача C. Возведение большого числа в степень ≡

Условие

Пусть имеется неотрицательное целое число A, представленное в виде массива своих цифр.
Требуется возвести его в некоторую заданную степень n.

Формат входного файла

Первая строка входного файла "input.txt" представляет собой десятичную запись числа A.
Следующая строка содержит показатель степени n.

Формат выходного файла

Выходной файл "output.txt" должен содержать результат возведения в степень,
представленный в десятичной системе счисления.

Ограничения

0 ≤ A ≤ 10⁵⁰, 0 < n ≤ 1000

Примеры тестов

10203756485819806252197658031528043601970
2

104116646421909761950282879573175588809976767764774752111453905887721451787880900

55786
17

490827381405222212342433355512086149590506305271663102056527621790991920279453696

Задача D. Пекарня ≡

Условие

Пекарня города Малоярославца способна произвести до c_i буханок хлеба в i-ый день. При этом каждая буханка хлеба обойдется пекарне в f_i условных Малоярославских долларов. Известно, что для обеспечения города продовольствием в день требуется d_i буханок хлеба, которые успешно будут употреблены населением. Оставшиеся буханки отправляются на склад и могут быть использованы в следующие дни. На складе можно в ночь с i ого на i + 1 день хранить не более g_i буханок, при этом хранение каждой буханки хлеба на складе обойдется пекарне в e_i Малоярославских долларов.

Ваша задача — определить наименьшее количество денег, которое пекарня потратит на производство и хранение, чтобы обеспечить Малоярославец хлебом в течение n дней.

Формат входного файла

В первой строке содержится натуральное число n. Далее в n строках содержатся числа c_i, f_i, d_i. Затем в n − 1 строках содержатся числа g_i, e_i.

Формат выходного файла

Выведите единственное число — минимальное количество денег, необходимое пекарне. Если удовлетворить требованиям города невозможно, выведите -1.

Ограничения

1 ≤ n ≤ 10⁵;

0 ≤ c_i, f_i, d_i, g_i, e_i ≤ 10⁹;

Примеры тестов

3
10 1 1
2 2 2
10 10 8
7 2
6 5

73