Қаҳва рецептлари

Каренда $n$ та қаҳва рецепти бор: $i$-рецепт қаҳвани $l_i$ дан $r_i$ градусгача (иккала чегара ҳам киради) қайнатишни тавсия қилади. Бутун сон ҳарорат камида $k$ та рецепт тавсия қилса, қулай дейилади.

Карен $q$ та савол беради: $a$ дан $b$ градусгача (иккала чегара ҳам киради) нечта қулай бутун ҳарорат бор?

Биринчи қаторда $n$, $k$, $q$ ($1 \le k \le n \le 2 \cdot 10^5$, ). Кейинги та қаторда ва , кейин та қаторда ва (, ).

Ҳар бир савол учун алоҳида қаторда битта сон.

Икки босқичли префикс. Фарқ массиви: ҳар бир рецепт учун $d_{l_i} \mathrel{+}= 1$, $d_{r_i + 1} \mathrel{-}= 1$; нинг префикс йиғиндиси ҳар бир ҳароратни нечта рецепт тавсия қилишини беради. Кейин , агар шу сон бўлса, ва нинг префикс йиғиндиси билан ҳар бир савол .