B. Diamond Hands
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У компании «Бриллиантовые руки» длинная и неоднозначная история. Начиная со дня основания, у нее было много и удачных, и неудачных дней. Для простоты будем считать, что в удачный день цена акции компании увеличивалась на единицу, а в неудачный день — уменьшалась на единицу. Как это часто бывает, удачные для компании дни шли длинными подряд идущими отрезками. Впрочем, то же самое можно сказать и про неудачные дни. Третьего не дано: каждый день был либо удачным, либо неудачным.

Вы хотите понять, какие отрезки дней были для компании удачными, а какие неудачными. Чтобы это сделать, вы добыли исторические данные цен акций компании в виде $$$n$$$ пар $$$(d_i, p_i)$$$, означающие, что через $$$d_i$$$ дней после выпуска акций разница с изначальной ценой составляла $$$p_i$$$ единиц ($$$p_i$$$ может быть произвольным целым числом, в том числе любым отрицательным).

Постройте описание истории компании в виде минимального числа отрезков удачных или неудачных дней, либо определите, что в данных ошибка, и восстановить подходящую под данные историю невозможно. Если существует несколько ответов с минимальным числом отрезков, выведите любой из них.

Входные данные

Первая строка содержит число $$$n$$$ ($$$1 \le n \le 200\,000$$$). Следующие $$$n$$$ строк содержат пары чисел $$$d_i \; p_i$$$ ($$$1 \le d_i \le 10^8$$$; $$$-10^8 \le p_i \le 10^8$$$; $$$d_i \lt d_{i+1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$n - 1$$$).

Выходные данные

Если в исторические данные закралась ошибка, выведите $$$-1$$$. Иначе, в первой строке выведите $$$k$$$ — количество отрезков дней. В каждой из следующих $$$k$$$ строк выведите пару $$$l_i \; c_i$$$ ($$$1 \le l_i \le 10^8$$$; $$$c_i \in \{\t{+}, \t{-}\}$$$), означающую, что очередной отрезок длился $$$l_i$$$ дней и состоял из удачных дней, если $$$c_i = \t{+}$$$, либо из неудачных дней, если $$$c_i = \t{-}$$$.

Описание отрезков дней должно идти в их хронологическом порядке, начиная со дня выпуска акций и заканчивая в день $$$d_n$$$, то есть, сумма всех $$$l_i$$$ должна быть равна $$$d_n$$$.

Система оценки
{Баллы}{Ограничения}
16$$$n \le 2000$$$, если ответ существует, то $$$k = 1$$$
28$$$n \le 2000$$$, если ответ существует, то $$$k \le 2$$$
310$$$n \le 200\,000$$$, если ответ существует, то $$$k \le 2$$$
428$$$n \le 2000$$$, $$$d_i, p_i \le 2000$$$
517$$$n \le 2000$$$, $$$d_i, p_i \le 10^8$$$
631$$$n \le 200\,000$$$, $$$d_i, p_i \le 10^8$$$
Примеры
Входные данные
4
2 2
3 3
5 1
7 1
Выходные данные
3
3 +
3 -
1 +
Входные данные
2
3 -3
7 -3
Выходные данные
2
5 -
2 +
Входные данные
1
1 0
Выходные данные
-1
Примечание

В первом примере, первые три дня были удачными, а значит, через 2 дня после выпуска акций разница составляла 2, а через 3 дня после выпуска разница составляла 3. За тремя удачными днями следовали три неудачных, и после 5 дней разница с изначальной ценой стала равна 1, а через 6 дней цена сравнялась с исходной. Последний, седьмой день был успешным, и финальная разница, после 7 дней, равна 1.