Офисный сервер печати получил n заданий на печать. Задания пронумерованы от 1 до n в порядке поступления на сервер.

Для каждого задания известны:

• приоритет p_i,
• количество страниц c_i.

Все задания поступают на сервер в момент времени 0.

Сервер обслуживает задания по следующим правилам:

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

Принтер начинает работу в момент времени 0.

Для каждого задания, в порядке фактического завершения печати, требуется определить:

• номер задания,
• момент времени, когда его печать завершится.

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

Первая строка содержит одно целое число n — количество заданий.

В следующих n строках содержится по два целых числа p_i и c_i — приоритет и количество страниц у i-го задания.

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

Выведите n строк.

В i-й строке выведите два числа через пробел:

• номер задания, которое завершилось i-м по счёту,
• момент времени окончания его печати.

Ограничения

• 1 <= n <= 10^5
• 1 <= p_i <= 9
• 1 <= c_i <= 1000

Примеры

Пример 1

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

1

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

1 0

Пример 2

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

2

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

1 0
2 0