На координатной прямой Ox сидят n лягушек. Для каждой известны две величины: x_i и t_i — позиция и начальная длина языка i-й лягушки (гарантируется, что все позиции x_i различны). Последовательно в хронологическом порядке на прямую садятся m комаров. Для каждого комара известны два параметра p_j — координата точки, куда сел j-й комар, и b_j — размер j-го комара. Лягушки и комары представляют собой точки на координатной прямой.

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

Если в какой-либо момент времени комара может съесть несколько лягушек, то его съедает самая левая из лягушек (с минимальным x_i). Сразу после того как лягушка съедает комара, ее язык мгновенно вырастает на величину равную размеру этого комара. Возможно, после этого лягушка сможет съесть (и съедает) других комаров.

Выведите для каждой лягушки две величины — количество съеденных комаров и длину языка, после того как все комары сядут на прямую, а лягушки съедят всех комаров, которых смогут.

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