Известный ученый-самоучка Шурик изобрел машину времени и теперь хочет осуществить заветную мечту - стать свидетелем одного исторического события. Он уже было собрался ввести в машину желаемую дату, но обнаружил, что мощность машины сильно ограничена. А именно, по причине питания от бытовой электрической сети машина не может совершить переход более чем на K дней. Сообразив, что придется путешествовать через промежуточные даты, Шурик составил список интервалов времени в прошлом, куда попадать ему совершенно не хочется из-за войн, революций, эпидемий, катастроф и т.п. У Шурика нет времени на расчеты, поэтому он просит вас определить последовательность переходов во времени к желаемой дате с минимальным числом промежуточных дат или же сказать, что при данных условиях событие недостижимо. Учтите, что машина времени может совершать переходы во времени как вперед так и назад, но не может прыгнуть в дату позднее начала путешествия.
Входные данные.
В первой строке записана дата изобретения машины времени, которая является стартовой для путешествия. Во второй строке записана дата, в которую нужно попасть. Эта дата является более ранней, чем стартовая. В третьей строке записано неотрицательное целое K (1 ≤ K ≤ 10^9) - величина максимального прыжка машины времени. В следующей строке записано целое число M (0 ≤ M ≤ 60000) - количество нежелательных интервалов времени. В последующих M строках заданы сами интервалы: датой начала и датой конца (обе границы включаются в интервал). Интервалы могут пересекаться. Гарантируется, что дата начала любого интервала не превосходит дату его завершения. Все даты во входном файле корректны и заданы в формате ДД.ММ.ГОД, где год находится в интервале от 1 до 3*10^6. Даты начала и завершения интервалов разделяются ровно одним пробелом.
Все вычисления следует проводить в соответствии с обычным грегорианским календарем, то есть считать, что год високосный, если он делится на 4, но не делится на 100 или год делится на 400. Например, годы 2012, 2000 - високосные, а 2007, 1900 - нет.
Гарантируется, что даты начала и конца путешествия не попадают ни в один из заданных интервалов.
Выходные данные.
В случае если желаемой даты достичь нельзя, выведите "NO SOLUTION". В противном случае выдайте в первой строке минимальное число дат в путешествии (включая начальную и конечную). Если это количество не превосходит 10^4, в следующих строках выведите сами даты по одной в строке, следуя формату, описанному для входных данных.
Примеры:

	input.txt	output.txt
Пример #1	30.07.1988 23.07.1988 2 2 26.07.1988 26.07.1988 22.06.1941 09.05.1945	5 30.07.1988 29.07.1988 27.07.1988 25.07.1988 23.07.1988
Пример #2	12.04.2006 01.01.1 1 0	732413

Ограничение времени для 32-х битного компилятора: 2 секунд
Ограничение времени для 16-и битного компилятора: 8 секунд
Ограничение памяти: 64 мегабайта
Входной файл: input.txt
Выходной файл: output.txt
Про компиляторы можно почитать здесь