24032번 - 깔때기와 비커

경기과학고에는 많은 종류의 실험 도구가 있다. 학교를 돌아다니던 재민이는 그 중 여러 모양의 깔때기들과 여러 크기의 비커들에 관심을 가지게 되어 이를 갖고 장난을 치기로 결심하였다.

장난도 계획을 세워서 쳐야 한다고 생각했던 재민이는 깔때기 $N$개를 한 층에 하나씩 $N$층으로 배치한 뒤, 움직이지 않도록 클램프로 고정하였다. 그 후, 가장 위 깔때기부터 1번, 2번,..., $N$번으로 번호를 매겼다. 이때 $i$번째 깔때기는 $L_i$와 $R_i$사이의 좌표로 떨어지는 액체를, $M_i$와 $M_i+1$사이의 좌표로 모은다. 모든 깔때기들은 $L_i \leq M_i<R_i$를 만족한다.

재민이는 이제 물을 이용해 장난을 본격적으로 $Q$번 쳐보려 한다. $i$번째 장난에서는 $S_i$번째 깔때기가 있는 층 위로 균일하게 전체 범위에 단위 길이당 1의 물을 뿌리고, $E_i$번째 깔때기가 있는 층 바로 밑에 왼쪽과 오른쪽 좌표가 각각 $X_i$, $Y_i$인 비커를 설치하여 얼마의 물이 비커에 모이는지 측정하기로 했다.

물론, 실험도구를 가지고 장난을 치는 것은 절대로 해서는 안되는 일이기에 여러분은 재민이를 막아야 한다. 재민이는 아마 자신이 세운 $Q$개의 계획에 대해서 비커에 물이 얼마나 모일지 여러분이 먼저 계산해서 알려주게 된다면, 이 장난에 흥미를 잃고 자습이나 하러 갈 것 같다. $Q$개의 계획에 대한 답을 재민이가 진짜로 물을 뿌리기 전에 빠르게 구해보자.

첫 줄에 깔때기의 수 $N$과 재민이가 세운 계획의 수 $Q$가 주어진다.($1 \leq N, Q \leq 500,000$)

다음 줄부터 $N$개의 줄에 걸쳐 깔때기의 위치에 대한 정보가 "$L_i$ $M_i$ $R_i$"의 형태로 주어진다. ($0 \leq L_i \leq M_i<R_i \leq 10^9$)

다음 줄부터 $Q$개의 줄에 걸쳐 재민이가 칠 장난에 대한 정보가 "$S_i$ $E_i$ $X_i$ $Y_i$"의 형태로 주어진다. ($1 \leq S_i \leq E_i \leq N$, $0 \leq X_i \leq Y_i \leq 10^9$)

각 장난에 대해 비커에 물이 얼마나 모일 지 답을 한 줄에 하나씩 출력한다.