Космическое сновидение

Аня любит читать книги, недавно ей посоветовали книгу известного физика-теоретика о чёрных дырах. Прочитав пару глав, она легла спать, и ей приснился странный сон.

Во сне девочка увидела систему из планет и чёрных дыр, местоположение которых можно представить на оси Ox. Как известно, чёрные дыры могут поглощать другие космические тела, в данной системе это свойство также сохраняется, причём каждая чёрная дыра действует на расстояние w_i и имеет мощность p_i. Пусть d − расстояние между планетой и чёрной дырой, равное модулю разности их координат. Чёрная дыра будет оказывать воздействие на эту планету только в том случае, если d ≤ w_i, при этом она будет поглощать планету с силой p_i - d. Может оказаться так, что на планету воздействует несколько чёрных дыр, в таком случае считается, что планета будет поглощена той чёрной дырой, которая действует на неё с наибольшей силой, при наличии нескольких таких чёрных дыр, планета может быть поглощена любой из них, в таком случае считается, что заранее предсказать исход невозможно.

Аня недавно начала заниматься олимпиадным программированием, поэтому, когда она проснулась, она захотела узнать для каждой планеты, какая чёрная дыра её поглотит.

Подумав некоторое время, девочка поняла, что эта задача ей не под силу, поэтому попросила вас помочь ей найти решение.

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

Первая строка входного файла INPUT.TXT содержит число n (1 ≤ n ≤ 2·10⁵) − количество небесных тел. Каждая из следующих n строк содержит информацию об очередном небесном теле:

• планета задаётся в формате «1 x_i», где x_i − координата i-й планеты (-10⁹ ≤ x_i ≤ 10⁹).
• чёрная дыра описывается в формате «2 x_j p_j w_j», где параметрам соответствуют − координата j-й черной дыры, мощность и дальность её воздействия (-10⁹ ≤ x_j ≤ 10⁹; 1 ≤ w_j < p_j ≤ 2·10⁹).

Все числа во входных данных являются целыми. Гарантируется, что существует хотя бы одна планета и в каждой точке может находиться не более чем один космический объект.

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

В первой строке выходного файла OUTPUT.TXT выведите одно число k − количество планет во входных данных.

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

Планеты и чёрные дыры нумеруются с единицы независимо друг от друга в том порядке, в котором заданы во входных данных.

Примеры

№	INPUT.TXT	OUTPUT.TXT	Пояснение
1	5 1 4 2 2 6 3 2 -1 10 5 1 5 1 -4	3 2 1 2
2	4 1 3 2 6 4 3 2 1 3 2 1 -2	2 1 -1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!