У компании «Бриллиантовые руки» длинная и неоднозначная история. Начиная со дня основания, у нее было много и удачных, и неудачных дней. Для простоты будем считать, что в удачный день цена акции компании увеличивалась на единицу, а в неудачный день — уменьшалась на единицу. Как это часто бывает, удачные для компании дни шли длинными подряд идущими отрезками. Впрочем, то же самое можно сказать и про неудачные дни. Третьего не дано: каждый день был либо удачным, либо неудачным.
Вы хотите понять, какие отрезки дней были для компании удачными, а какие неудачными. Чтобы это сделать, вы добыли исторические данные цен акций компании в виде $$$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$$$.
| {Баллы} | {Ограничения} | |
| 1 | 6 | $$$n \le 2000$$$, если ответ существует, то $$$k = 1$$$ |
| 2 | 8 | $$$n \le 2000$$$, если ответ существует, то $$$k \le 2$$$ |
| 3 | 10 | $$$n \le 200\,000$$$, если ответ существует, то $$$k \le 2$$$ |
| 4 | 28 | $$$n \le 2000$$$, $$$d_i, p_i \le 2000$$$ |
| 5 | 17 | $$$n \le 2000$$$, $$$d_i, p_i \le 10^8$$$ |
| 6 | 31 | $$$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.
