4-й этап Республиканской олимпиады по информатике 2022-2023, 2-й тур

Есеп D. Массив және сұраныстар

Ограничение по времени:

1.5 seconds

Ограничение по памяти:

256 megabytes

Абай сізге аңызсыз қарапайым есеп әкелді. $N$ натурал саннан тұратын $A$ массиві бар. Оған қоса, $L, R$ түріндегі $Q$ сұраныстары берілген. Сұранысқа жауап — бұл $A_L$, $A_{L+1}$, ..., $A_R$ тізбегінін ішінде, $X$, $2X$, $4X$, ..., $2^K \cdot X$ сандарының бәрі кездесетіндей, $X$ натурал саны табылса, $K$ ($K \ge 0$) санының ең үлкен мәні. Ескерту: натурал сан деп нөлден үлкен бүтін сандарды айтамыз.

Формат входного файла

Бірінші жолда екі $N$ және $Q$ ($1 <= N, Q <= 5 \cdot 10^5$) натурал сандары берілген. Екінші жолда $A$ массиві берілген ($1 <= A_i <= 10^{18}$). Үшінші жолдан бастап сұраныстар, $L$, $R$ ($1 <= L <= R <= N$), беріледі. Әр сұраныс бөлек жолда берілген.

Формат выходного файла

$Q$ жолдарын шығарыңыз, $i$-ші жолда $i$-ші сұранысқа жауап болуы керек.

Пример:

Вход

6 3
6 9 12 24 18 9
2 3
4 6
1 5

Ответ

0
1
2

Замечание

Мысалға түсініктеме: Екінші сұраныста, 18 және 9 сандарын таңдасақ, $K = 1, X = 9$ шығады. Үшінші сұраныста — 6, 12, 24 ($K = 2, X = 6$). ( Abay Baimukanov )