No.2961 Shiny Monster Master
タグ : / 解いたユーザー数 58
作問者 : ねしん / テスター : 👑 p-adic
ストーリー
色違い絶賛沼っている最中です。助けてください。$1$ 周 $20$ 分くらいかかるんですよ...
問題文
大人気モンスターのゲームが発売されました。そのゲームではまれに色違いと呼ばれる珍しいモンスターが出現します。
このゲームでは $R$ 秒周期のカウンターが使われています。ゲームを起動した時点ではカウンターの値は $0$ であり、起動した直後から $1$ 秒ごとに $1$ ずつ増えていきます。ただし、カウンターの値が $R-1$ までくると $0$ に戻ります。
また、色違いはカウンターが $A_i(1 \leq i \leq N)$ の時に必ず出現し、それ以外では出現しないことがわかっています。
ここで、今から $Q$ 個のクエリが渡されます。$i$ 番目 $(1 \leq i \leq Q)$ のクエリでは $l_i,r_i$ が与えられます。以下の問いに答えてください。
入力
$R$ $N$ $A_1$ $\cdots$ $A_N$ $Q$ $l_1$ $r_1$ $\ldots$ $l_Q$ $r_Q$
出力
$Q$ 行出力してください。$i(1\leq i \leq Q)$ 行目には $i$ 番目のクエリの答えを出力してください。
サンプル
サンプル1
入力
5 2 1 3 3 1 4 13 20 89 90
出力
2 3 0
$2$ つ目のクエリでは、$13$ 秒後のときカウンターが $3$ となり、色違いが出現します。$16$ 秒後でカウンターが $1$、$18$ 秒でカウンターが $3$ となるので、全部で $3$ 回チャンスがあります。
なお、ゲームを起動してから $l_i$ 秒後、$r_i$ 秒後に出現する色違いも含みますので注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。