Вадим — большой фанат кусочно-линейных функций. Они имеют свои ограничения, и не любую функцию можно представить как кусочно-линейную. Вадим вам с радостью расскажет, что это такое.
Функция называется кусочно-линейной, если её график можно представить ломаной из $$$n$$$ вершин. А именно, она задаётся $$$n$$$ парами чисел $$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$, которые являются координатами вершин ломаной. Обязательно должно выполняться условие $$$$$$x_1 < x_2 < x_3 < \ldots < x_n.$$$$$$
Этот набор точек задаёт функцию от одного аргумента, значение которой в $$$x_i$$$ равно $$$y_i$$$, а на промежутках между этими точками она линейная. Область определения такой функции — это отрезок $$$[x_1, x_n]$$$.
Валя придумал свой класс функций с одной переменной, которые он назвал модульными. Модульная функция состоит из $$$n$$$ слагаемых, каждое из которых имеет один из двух видов: $$$|a_i \cdot x + b_i|$$$ или $$$-|a_i \cdot x + b_i|$$$. Здесь $$$x$$$ — переменная, а $$$a_i$$$ и $$$b_i$$$ — параметры функции, а $$$| \ldots |$$$ обозначает взятие по модулю. Таким образом, модульная функция с $$$n$$$ слагаемыми имеет вид $$$$$$\pm|a_1 x + b_1| \pm |a_2 x + b_2| \pm \ldots \pm |a_n x + b_n|.$$$$$$
Вадим захотел проверить, не хуже ли модульные функции его любимых кусочно-линейных. Он принёс кусочно-линейную функцию с $$$n$$$ вершинами. Постарайтесь теперь найти модульную функцию с ровно $$$n$$$ слагаемыми, которая будет тождественна равна данной кусочно-линейной на отрезке $$$[x_1, x_n]$$$.
В первой строке дано целое число $$$n$$$ — количество вершин ломаной $$$(2 \le n \le 10^5)$$$.
Далее идёт $$$n$$$ строк, в каждой из которых через пробел даны два целых числа $$$x_i$$$, $$$y_i$$$ — координаты очередной вершины ($$$-10^5 \le x_i, y_i \le 10^5$$$).
Гарантируется, что координаты $$$x_i$$$ идут строго по возрастанию, то есть $$$$$$x_1 < x_2 < x_3 < \ldots < x_n.$$$$$$
Выведите в единственной строке модульную функцию из ровно $$$n$$$ слагаемых, тождественно равную данной кусочно-линейно функции на отрезке $$$[x_1, x_n]$$$. Придерживайтесь формата, показанного в примерах.
Функция должна состоять из $$$n$$$ слагаемых $$$|a_i x + b_i|$$$, разделённых знаками + и - (коды 43 и 45). Разрешается перед первым слагаемым поставить ведущий минус. Каждое слагаемое должно быть взято по модулю двумя символами | (код 124). Внутри слагаемого должен быть знак + (или -, если $$$b_i$$$ отрицательно). Левый операнд состоит из вещественного числа $$$a_i$$$ и переменной $$$x$$$ (код 120); знак умножения между ними не нужно писать, он подразумевается. Опускать $$$a_i$$$ или $$$b_i$$$ нельзя, даже если $$$a_i = 1$$$ или $$$b_i = 0$$$; нельзя также опускать левый операнд, если $$$a_i = 0$$$.
Таких слагаемых должно быть ровно $$$n$$$. Разрешено использовать слагаемые, тождественно равные нулю. Они могут быть записаны как |0x+0|.
Размер выходного файла должен быть не больше $$$8$$$ МБ. Ответ считается правильным, если в любой точке отрезка $$$[x_1, x_n]$$$ значение вашей модульной функции отличается от значения данной кусочно-линейной не более, чем на $$$0.01$$$.
2 1 0 2 1
-|0x-1|+|1x+0|
2 0 1 1 2
|1x-0|+|0x+1|
3 -1 1 0 -1 1 0
|-0.5x+1|-|0x-2|+|-1.5x-0|
Иллюстрация к третьему примеру: