#446 나머지 세기

문제를 불러오는 중...

지문, 최근 제출, 제출 폼을 준비하고 있습니다.

#446 나머지 세기 | DOJ

Statement

You are given a sequence $A$ of length $N$ . Process $Q$ queries of the following form.

i j x y: Count the elements among $A_i,A_{i+1},\cdots,A_j$ whose remainder modulo $x$ is $y$ .

The input is given in the following format:

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

Each test case is given in the following format:

$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$

For each test case, print the answer to every query on its own line.

#	점수	제한
1	5	$N,Q \leq 2\,000$ , and the sums of $N$ and $Q$ over all test cases do not exceed $2\,000$ each.
2	3	$i_q=j_q$ for every query $1 \leq q \leq Q$ .
3	11	$y_q$ is the same for every query.
4	29	$i_q=1$ and $j_q=N$ for every query $1 \leq q \leq Q$ .
5	52	No additional constraints.

입력

출력