Сізге ұзындығы \(n\) болатын \(a\) массиві берілген. Оның кейбір элементтері \(-1\)-ге тең; әрбір осындай элементті тәуелсіз түрде кез келген теріс емес бүтін санға ауыстыруға болады.

Ұзындығы \(m = r - l + 1\) болатын \(b = (a_l, a_{l+1}, \dots, a_r)\) ішкі массивін қарастырайық.

Егер \(0\)-ден \(m-1\)-ге дейінгі сандардың қандай да бір \(p\) ауыстыруы, яғни \([0, m-1]\) аралығындағы әрбір сан дәл бір рет кездесетін массив, табылып, онда \(1\)-ден \(m\)-ге дейінгі әрбір \(i\) позиция үшін келесі шарт орындалса, онда \(b\) ішкі массивін \(k\)-жақсы деп атаймыз:

• егер \(b_i \ne -1\) болса, онда \(p_i \bmod k = b_i\);

• егер \(b_i = -1\) болса, онда бұл позицияда ешқандай шектеу жоқ.

Басқаша айтқанда, \(0\)-ден \(m-1\)-ге дейінгі сандарды позицияларға солай орналастыру керек, барлық алдын ала берілген позицияларда \(k\) модулі бойынша қалдық сол мәнге тең болатындай.

Әрбір \((l, r)\) сұранысы үшін \(a_l, a_{l+1}, \dots, a_r\) ішкі массиві қанша \(k\) мәні үшін \(k\)-жақсы болатынын анықтау керек. Қолайлы \(k\) мәндерінің саны шексіз болуы мүмкін екеніне назар аударыңыз.

Енгізу

Бірінші жолда екі бүтін сан \(n\) және \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) берілген — массивтің ұзындығы және сұраныстар саны.

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \dots, a_n\) берілген (\(a_i = -1\) немесе \(0 \le a_i \le 2 \cdot 10^5\)).

Келесі \(q\) жолдың әрқайсысында екі бүтін сан \(l\) және \(r\) (\(1 \le l \le r \le n\)) берілген — ішкі массивтің шекаралары.

Шығару

Әрбір \((L, R)\) сұранысы үшін \(a_L, a_{L+1}, \dots, a_R\) ішкі массиві \(k\)-жақсы болатын барлық оң бүтін \(k\) сандарының санын шығарыңыз. Егер мұндай \(k\) мәндері шексіз көп болса, \(-1\) шығарыңыз.

Мысалдар

Енгізу 1

6 5
1 0 -1 0 1 0
2 4
4 6
1 3
1 6
3 6

Жауап 1

2
1
-1
1
2

Ескертпелер

\((2, 4)\) сұранысы үшін ішкі массив \([0, -1, 0]\) болады. Тек \(k = 2\) және \(k = 1\) ғана сәйкес келеді, сондықтан жауап \(2\).

\((4, 6)\) сұранысы үшін ішкі массив \([0, 1, 0]\) болады. Тек \(k = 2\) ғана сәйкес келеді, сондықтан жауап \(1\).

\((1, 3)\) сұранысы үшін ішкі массив \([1, 0, -1]\) болады. Кез келген жеткілікті үлкен \(k\) үшін қолайлы ауыстыруды таңдауға болады, сондықтан мұндай \(k\) мәндері шексіз көп, ал жауап \(-1\).