JOI 아카데미에는 1번부터 N번까지의 번호가 매겨진 N명의 학생이 있습니다. 곧 JOI 아카데미에서 선물 교환 파티가 열릴 예정입니다. 각 학생은 파티에 가져올 선물을 준비했습니다. 학생 i(1 ≤ i ≤ N)가 가져올 선물의 가치는 Ai입니다. 학생들은 자신의 선물보다 너무 가치가 낮은 선물을 받는 것을 원치 않습니다. 구체적으로, 학생 i는 가치가 Bi보다 작은 선물을 받으면 불만족스러워할 것입니다. 여기서 Bi < Ai는 항상 성립합니다.

그러나 N명의 학생 중 일부는 파티에 실제로 참가하지 않을 수도 있습니다. JOI 아카데미의 회장인 K는 Q개의 가능한 그룹을 고려하고 있으며, 각 그룹은 선물 교환 파티에 참가할 그룹으로 간주됩니다. j번째 그룹(1 ≤ j ≤ Q)은 Rj에서 Lj까지의 학생들로 구성됩니다.

2명 이상의 학생들로 구성된 어떤 그룹에서, 그 그룹 내에서 아무도 자신의 선물을 받거나 불만족하지 않으면서 선물을 교환할 수 있다면, 그 그룹은 "선물 교환 가능(gift exchangeable)"하다고 합니다. 좀 더 구체적으로, m명(m ≥ 2)의 학생들 p1, p2, ..., pm으로 구성된 그룹이 다음 조건을 만족할 경우에만 선물 교환 가능하다고 할 수 있습니다. 여기서 q1, q2, ..., qm은 p1, p2, ..., pm의 순열을 나타내며, qk(1 ≤ k ≤ m)는 학생 pk에게 선물을 주는 학생의 번호를 의미합니다.

모든 k(1 ≤ k ≤ m)에 대해, pk ≠ qk.
모든 k(1 ≤ k ≤ m)에 대해, Aqk ≥ Bpk.

K 회장은 선물 교환 파티가 성공적으로 이루어지길 바라고 있으며, 각 Q개의 그룹이 선물 교환이 가능한지 여부를 확인하고자 합니다.

#8060 upload - done - how_to_reg - call_split 서브태스크

선물 교환 timer 1s memory 1024MB

#8060
서브태스크

선물 교환 1s 1024MB