나머지 세기

길이가 $N$인 수열 $A$가 주어진다. 다음 쿼리를 $Q$번 수행하여라.

• i j x y: $A_i,A_{i+1},\cdots,A_j$ 가운데 $x$로 나눈 나머지가 $y$인 원소의 개수를 구한다.

입력은 다음과 같은 형식으로 주어진다.

$T$ case$_1$ case$_2$ $\vdots$ case$_T$

각 테스트 케이스는 다음과 같은 형식으로 주어진다.

$N\ Q$ $A_1\ A_2\ \cdots\ A_N$ $i_1\ j_1\ x_1\ y_1$ $i_2\ j_2\ x_2\ y_2$ $\vdots$ $i_Q\ j_Q\ x_Q\ y_Q$

각 테스트 케이스의 각 쿼리에 대한 답을 한 줄에 하나씩 출력한다.

• $1 \leq T \leq 20$.
• $1 \leq N \leq 200\,000$.
• $1 \leq Q \leq 1\,000\,000$.
• $0 \leq A_i \leq 450$ ($1 \leq i \leq N$).
• $1 \leq i_q \leq j_q \leq N$ ($1 \leq q \leq Q$).
• $1 \leq x_q \leq N$ ($1 \leq q \leq Q$).
• $0 \leq y_q < x_q$ ($1 \leq q \leq Q$).
• 모든 테스트 케이스에 대한 $N$의 합은 $200\,000$ 이하이다.
• 모든 테스트 케이스에 대한 $Q$의 합은 $1\,000\,000$ 이하이다.