Каких только странных задач не приходится решать школьникам! При этом некоторые из этих задач, являясь абсолютно бессмысленными, требуют достаточно много времени на решение. Так в одной из школ в качестве домашнего задания была дана следующая задача – представить натуральное число в виде суммы степеней двух натуральных чисел. Казалось бы, ничего сложного. Однако, выписав в тетрадку все варианты, когда хотя бы одно из чисел, возводимых в степень, или хотя бы один из показателей равны 1, умные, но ленивые школьники поняли, что для того, чтобы найти остальные варианты, им придется перебрать очень много случаев и об отдыхе на ближайшее время можно забыть.
Тогда они решили за умеренную плату заказать выполнение домашнего задания. Почему бы Вам не заработать немного денег, написав программу, которая найдет остальные варианты?
В первой строке одно натуральное число N, 1 ≤ N ≤ 2000000000.
В первой строке одно натуральное число K – количество различных способов представления числа N в виде a^x+b^y таких, что a, b, x, y – натуральные числа, ни одно из них не равно 1, a ≥ b и, если a = b, то x ≥ y.
Далее K строк по четыре числа a, x, b, y через пробел, каждая из которых заканчивается переходом на новую строку, – способы представления числа N в заданном виде. Эти четверки чисел упорядочены между собой по возрастанию a, а в случае равенства a – по b, в случае равенства a и b по x.