Sequence and Queries 7

You are given a sequence $A_1, A_2, \dots, A_N$ of length $N$ and an integer $K$. Write a program that answers the following query.

• l r: print the length of the longest contiguous subsequence with $l \le i \le j \le r$ and $(A_i + A_{i+1} + \cdots + A_j) \bmod K = 0$. If no subsequence satisfies the condition, the length is 0.

The first line contains the size of the sequence $N$ ($1 \le N \le 100\,000$) and $K$ ($2 \le K \le 1\,000\,000$).

The second line contains $A_1, A_2, \dots, A_N$. ($1 \le A_i \le 1\,000\,000\,000$)

The third line contains the number of queries $M$ ($1 \le M \le 100\,000$).

Each of the next $M$ lines contains one query $l$, $r$. ($1 \le l \le r \le N$)

Print the answer to each query on its own line.