6. Модульная рекурентная последовательность

Простой старшеклассник японской школы по имени Фибоначчи придумал рекуррентную последовательность $\{f_i\}$, у которой $f_0 = 0$, $f_1 = 1$, а $f_n = (af_{n-1} + bf_{n-2}) \mod p$, где $p$ $-$ простое число и $1 \leq a, b < p$. Он изучил очень много ее свойств и решил выступить с докладом на фестивале школьных кружков. Но, к сожалению, на эту выставку приехала делегация 9 «В» класса школы имени Валентина Стрыкало, и девочка из этого класса по имени Альбина задала ему вопросы вида: «А есть ли такая позиция $i$, что $f_i = x$, а $f_{i+1} = y$»? Фибоначчи, безусловно, знает свою последовательность наизусть и легко может ответить на все ее вопросы, но у него есть более интересные варианты досуга. Поэтому он просит вас ему помочь и написать программу, которая ответит на все вопросы Альбины.

В первой строке входных данных заданы 3 целых числа $p, a, b$ ($0 < a, b < p \leq 10^6$), а во второй $-$ одно целое число $1 \le q \le 10^6$ $-$ количество запросов. В последующих $q$ строках представлены вопросы Альбины, каждый из которых представляется парой чисел $x$ и $y$ ($0 \leq x, y < p$).

Выведите отверы на запросы в порядке, в котором запросы заданы во входных данных. Ответом на запрос является число $-1$, если пара $(x,y)$ не встречается подряд в последовательности, или единственное натуральное число $t_i$ $-$ ответ на вопрос Альбины, если подходящих чисел несколько, то выведите минимальное.