Мальчик Валера зарегистрировался на сайте Codeforces под ником Valera и написал свой первый Codeforces Round #300. Он похвастался другу Аркадию, что за свое первое соревнование набрал целых x баллов. Но Аркадий не поверил на слово другу и решил проверить, действительно ли Валера мог показать такой результат.

Он знает, что соревнование под номером 300 было необычным, поскольку в нем было всего две задачи. Соревнование длилось t минут, минуты нумеруются с нуля. Первая задача имела начальную стоимость a баллов, и каждую минуту эта стоимость уменьшалась на d_a баллов. Вторая задача имела начальную стоимость b баллов, и каждую минуту эта стоимость уменьшалась на d_b баллов. Таким образом, как только закончится нулевая минута соревнования, первая задача будет стоить a - d_a баллов, а вторая — b - d_b баллов. Гарантируется, что в любую минуту соревнования каждая задача имеет неотрицательную стоимость.

Аркадий просит Вас узнать, мог ли Валера получить за это соревнование ровно x баллов. При этом стоит считать, что Валера мог решить любое количество из предложенных задач. Также следует считать, что по каждой задаче Валера сделал не более одной попытки, причем обе задачи он мог отправить на проверку в одну и ту же минуту соревнования, начиная с минуты под номером 0 и заканчивая минутой под номером t - 1. Обращаем внимание, что посылать решение ровно через t минут после начала соревнование Валера не может.