깔때기와 비커
시간 제한4초메모리 제한1024 MB
층층이 쌓인 N개의 깔때기가 [L, R] 구간의 물을 받아 [M, M+1] 구간으로 내보낼 때, 각 질의마다 E번 깔때기 아래 비커에 모이는 물의 양을 구합니다.
문제
경기과학고에는 많은 종류의 실험 도구가 있다. 학교를 돌아다니던 재민이는 여러 모양의 깔때기와 여러 크기의 비커에 관심을 갖게 되었고, 이것들을 가지고 장난을 치기로 했다. 장난에도 계획이 필요하다고 생각한 재민이는 깔때기 개를 한 층에 하나씩 층으로 배치하고, 움직이지 않도록 클램프로 고정했다. 가장 위 깔때기부터 1번, 2번, ..., 번으로 번호를 붙였다. 번째 깔때기는 와 사이의 좌표로 떨어지는 액체를 받아 와 사이의 좌표로 모은다. 모든 깔때기는 를 만족한다.
재민이는 이제 물을 이용해 이 장난을 번 쳐 보려 한다. 번째 장난에서는 번째 깔때기가 있는 층 위로 전체 범위에 단위 길이당 1의 물을 균일하게 뿌린다. 그다음 번째 깔때기가 있는 층 바로 밑에 왼쪽 좌표가 , 오른쪽 좌표가 인 비커를 설치하고, 비커에 물이 얼마나 모이는지 측정한다.
재민이가 실제로 물을 뿌리기 전에, 개의 계획 각각에 대한 답을 구하라.
입력
첫 줄에 깔때기의 수 과 계획의 수 가 주어진다().
다음 개의 줄에 깔때기의 위치 정보가 " " 형태로 주어진다().
다음 개의 줄에 장난 정보가 " " 형태로 주어진다(, ).
출력
각 장난에 대해 비커에 모이는 물의 양을 한 줄에 하나씩 출력한다.