시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 256 MB | 41 | 8 | 6 | 17.647% |
You are given a sequence $a_1, a_2, \ldots, a_n$ consisting of positive integers. You have to answer $q$ queries. A query is defined by a triplet of numbers $(l, r, x)$. For each query, you have to find the largest $p$ such that $l \leq p \leq r$ and $a_p$ is coprime with $x$, or determine that there is no such $p$.
The first line of the input contains two integers $n$ and $q$ ($1 \leq n, q \leq 100\,000)$.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 100\,000$).
The next $m$ lines contain queries. The $i$-th of these lines contains three integers $l_i$, $r_i$ and $x_i$ ($1 \le l_i \le r_i \le n$, $1 \le x \le 100\,000$).
For each query, output the answer to it on a separate line.
5 4 1 2 3 4 6 1 5 2 1 1 1 4 5 2 3 5 3
3 1 -1 4