Поликарп купил волшебную книгу, состоящую из $$$n$$$ страниц. Все страницы пронумерованы по очереди целыми числами от $$$1$$$ до $$$n$$$. Поликарп хочет с помощью этой книги наколдовать себе пятерку в четверти по информатике.
Чтобы произошло волшебство, Поликарп должен выбрать страницу $$$x$$$ и прочитать все страницы книги, начиная со страницы $$$x$$$ и заканчивая последней страницей с номером $$$n$$$.
Также Поликарп знает, что цифры $$$a$$$ и $$$b$$$ являются волшебными. Если окажется так, что среди прочитанных Поликарпом страниц ровно $$$k$$$ номеров страниц заканчиваются на цифры $$$a$$$ или $$$b$$$, то произойдет чудо, и Поликарп получит пятерку в четверти по информатике.
Так как Поликарп очень ленивый, он не хочет читать очень много страниц, поэтому среди всех подходящих страниц, с которых Поликарп может начать читать книгу, он выберет страницу с наибольшим номером.
Перед вами стоит задача определить наибольший номер страницы $$$x$$$, с которой Поликарп должен начать читать книгу, чтобы ровно $$$k$$$ номеров страниц, начиная со страницы $$$x$$$ и заканчивая страницей $$$n$$$, заканчивались на цифры $$$a$$$ или $$$b$$$.
В первой строке следуют четыре целых числа $$$n$$$, $$$k$$$, $$$a$$$ и $$$b$$$ ($$$1 \le k \le n \le 10^{12}$$$, $$$0 \le a, b \le 9$$$, $$$a \neq b$$$) — количество страниц в книге, необходимое количество страниц, которые должны заканчиваться на цифры $$$a$$$ или $$$b$$$, а также сами цифры $$$a$$$ и $$$b$$$.
Следует обратить внимание, что входные и выходные данные в этой задаче могут не помещаться в стандартный $$$32$$$-битный тип данных. Необходимо использовать $$$64$$$-битный тип данных (long long в С++, int64 в Паскале, long в Java).
Если Поликарп не сможет с помощью книги наколдовать себе пятерку в четверти по информатике, выведите $$$-1$$$.
В противном случае, выведите наибольший номер страницы $$$x$$$, с которой Поликарп должен начать читать книгу, чтобы произошло волшебство, и он получил пятерку в четверти по информатике.
29 3 8 0
18
20 5 4 7
-1
1000000000000 1234 5 6
999999993835
В первом примере Поликарп должен начать читать книгу со страницы $$$18$$$. Тогда ровно три номера прочитанных страниц будут заканчиваться на $$$8$$$ или $$$0$$$: $$$18$$$-я, $$$20$$$-я и $$$28$$$-я страницы.
Во втором примере в книге всего четыре страницы, чьи номера заканчиваются на $$$4$$$ или $$$7$$$: страницы $$$4$$$, $$$7$$$, $$$14$$$ и $$$17$$$. Так как $$$k = 5$$$, Поликарп не сможет наколдовать себе пятерку в четверти по информатике.
