Построить интерполяционный кубический сплайн

Даны значения неизвестной функции в узлах равномерной сетки:

Постройте по этим данным интерполяционный кубический сплайн.

Интерполяционным кубическим сплайном для неизвестной функции называется функция s(x), удовлетворяющая следующим условиям:

1. Функция s(x) является многочленом третьей степени на каждом отрезке


2. Функция s(x) непрерывна на отрезке [A, B] с первыми двумя производными s'(x), s''(x).

3.

4.

Построение кубического сплайна сводится к решению трехдиагональной СЛАУ методом прогонки. В случае равномерной сетки, СЛАУ имеет вид

Коэффициенты могут быть найдены по формулам:



Требуется вычислить значения интерполяционного кубического сплайна s(x) в заданных точках s_0, s_1, ..., s_N.
Формат входных данных
В первой строке заданы два целых числа n и и два вещественных числа A и B — концы отрезка. В следующей строке заданы n + 1 вещественное число y_0, y_1, ..., y_n. Последняя строка содержит числа , принадлежащие отрезку [A, B]. Все вещественные числа в задаче не превосходят 1000 по абсолютной величине и заданы не более чем с тремя знаками после десятичной точки.
Формат выходных данных
Выведите N + 1 число — значения интерполяционного кубического сплайна в точках . Абсолютная или относительная погрешность результата не должна превышать


Примеры:
Вход
2 4 0 2
0 3 1
0 0.6 1 1.1 2
Выход
0.0000000000 2.2800000000 3.0000000000 3.0137500000 1.0000000000