Зарплата - 2

В одном государственном учреждении работают n сотрудников. Их фактические зарплаты равны d_i, но по закону всем сотрудникам положено платить одинаково, поэтому им всем официально выплачивают среднюю зарплату d, такую, чтобы общая сумма оставалась такой же, а потом сотрудники сами перераспределяют полученные деньги.

Короче, творится полный бардак. И чтобы этот бардак уменьшить, Самый Главный Начальник решил использовать недавно принятый закон «о материальной помощи», который позволяет любому сотруднику часть своей зарплаты (целое число рублей от 1 до d-1) передавать другому сотруднику в виде материальной поддержки. Однако по закону сотрудник, таким образом, может «помогать» только одному «малоимущему».

Например, если Петя и Вася получают по 100 рублей и Петя напишет заявление на передачу 30% своей зарплаты Васе, то Петя будет получать 70 рублей, а Вася - 130.

Теперь Самый Главный Начальник хочет узнать: кто, кому и сколько должен передавать, чтобы в результате все получали ровно столько, сколько нужно. Помогите ему это сделать.

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

Входной файл INPUT.TXT содержит целые числа n и d (1 ≤ n ≤ 10⁵, 1 ≤ d ≤ 10⁹), и далее n целых чисел d_i (1 ≤ d_i ≤ 10⁹). Сумма всех d_i равна n∙d.

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

В выходной файл OUTPUT.TXT выведите n пар целых чисел a_i и b_i, означающих, что сотрудник i передает сотруднику a_i часть своей зарплаты в размере b_i рублей. Если сотрудник i ничего никому не передает, выведите вместо a_i и b_i два нуля.

Примеры

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

[Обсуждение] [Все попытки] [Лучшие попытки]