B. Награда за головы
Виталий обожает азартные игры. Его любимая игра включает участников, пронумерованных от до . У каждого игрока есть два баланса: первый — это его выигрыш, второй — награда за его голову. Изначально выигрыш каждого игрока равен , а награда за голову — .
В игре происходит ровно последовательное событие, в каждом из которых участвуют два разных игрока, которые еще не выбыли из игры. Первый игрок выбивает второго. В результате этой операции к выигрышу первого игрока добавляется награда за голову второго, а к награде за голову первого прибавляется половина награды за голову второго. Второй игрок выбывает из игры и больше не может никого выбивать или быть выбитым.
Ваша задача — определить последовательность событий, которая минимизирует (или максимизирует) суммарный выигрыш всех игроков.
Входные данные
Первая строка содержит два целых числа и () — количество игроков и параметр, определяющий, для какого выигрыша решается задача. Значение соответствует минимальному выигрышу, — максимальному.
Выходные данные
Выведите строк. В -ой строке должно быть указано два целых числа и (), что означает, что игрок под номером выбил игрока на шаге .
Примеры
Примечание
Рассмотрим первый пример. Балансы игроков на каждом шаге:
Начальные балансы: .
Балансы после первого шага: .
Балансы после второго шага: .
Суммарный выигрыш игроков:
Рассмотрим второй пример. Балансы игроков на каждом шаге:
Начальные балансы: .
Балансы после первого шага: .
Балансы после второго шага: .
Суммарный выигрыш игроков:
Оценивание
В тестов .
В остальных тестов .