Задача A. Памятка водителю

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Водитель Авессалом Викторович работает на маршруте 77, который ходит на остров Русский. Часто пассажиры либо расплачиваются без сдачи, либо дают одну купюру. Во втором случае Авессалом Викторович должен рассчитать сдачу в зависимости от того, сколько билетов берёт пассажир.

Но под конец рабочего дня Авессалому Викторовичу становится трудно быстро вычислять сдачу из-за усталости. Поэтому он решил повесить себе памятку с указанием, сколько давать сдачи на каждую купюру. Известно, что билет стоит N рублей.

Авессалом Викторович просит вас ему помочь. Напишите программу, принимающую на вход число N и выводящую сдачу для всех возможных купюр и всех возможных количеств билетов, на которые хватит этой купюры. Возможные достоинства купюры — 50, 100, 500, 1000.

Формат входного файла

Входной файл содержит целое число N.

Формат выходного файла

Выходной файл должен содержать 4 блока. Для каждого блока необходимо вывести достоинство купюры, за которым должны следовать ноль или более пар целых чисел — количество билетов и сдача при таком количестве билетов. Блоки необходимо вывести по возрастанию достоинства купюры. Пары необходимо вывести по возрастанию количества билетов.

Ограничения

1 ≤ N ≤ 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1000
50
100
500
1000
1 0
2
450
50
100
500
1 50
1000
1 550
2 100

0.037s 0.009s 15