빔

당신은 구간 보관 서비스를 운영하고 있다. 현재 보관소에는 총 $N$개의 구간이 보관되어 있고, 이 중 $i$번째 구간은 수직선에서 $\[l\_i, r\_i]$로 나타난다.

보관소에 총 $Q$회의 레이저 폭격이 예고되었다! 이 중 $j$번째 레이저 빔의 피해 범위는 구간 $\[s\_j, e\_j]$로 나타낼 수 있다. 당신은 각 레이저 빔이 날아올 때마다, 보관된 구간을 적절히 옮겨서 빔에 맞는 구간이 없도록 해야 한다.

구체적으로, 보관된 각 구간 $\[l\_i, r\_i]$에 대해 적절한 정수 $x\_{ij}$를 정한다. 이 때 모든 $(i, j)$에 대해 $\[l\_i+x\_{ij}, r\_i+x\_{ij}]$와 $\[s\_j, e\_j]$가 겹치는 부분의 길이가 $0$이 되도록 해야 한다. 두 구간 $\[a, b]$와 $\[c, d]$가 겹치는 부분의 길이는 $\max(0, \min(b, d) - \max(a, c))$이다.

구간은 무겁기 때문에 기계를 사용하여 옮기는데, 한 번 옮길 때마다 (이동 거리) $\times$ (구간 길이) 만큼의 전기료가 나온다. 즉, $j$번 레이저 빔이 오기 전에 사용하는 전기료는 $\sum\_{i=1}^{N} (r\_i-l\_i)|x\_{ij}|$이다.

각 레이저 빔이 지나간 후에 당신은 옮겼던 모든 구간을 다시 원래 위치로 되돌려 놓는다. 옮길 때와 돌려놓을 때 모두 똑같이 비용이 발생함을 유의하라.

당신은 각 레이저 빔마다 최소한의 전기료를 사용하여 모든 구간을 안전하게 관리하려고 한다. 이때의 비용을 계산하여 보자.

첫째 줄에 구간의 개수 $N$과 예고된 레이저 폭격의 수 $Q$가 주어진다. ($1 \le N, Q \le 250\\,000$)

이후 $N$개의 줄에 걸쳐, 그 중 $i$번째 줄에는 $i$번째 보관된 구간의 양 끝점 $l\_i$와 $r\_i$가 주어진다. ($1 \le l\_i < r\_i \le 1\\,000\\,000$)

이후 $Q$개의 줄에 걸쳐, 그 중 $j$번째 줄에는 $j$번째 레이저 빔 피해 범위의 양 끝점 $s\_j$와 $e\_j$가 주어진다. ($1 \le s\_j < e\_j \le 1\\,000\\,000$)

입력으로 들어오는 모든 수는 정수이다.

각 레이저 빔에 대해, 현재 상태에서 모든 구간을 안전한 위치로 옮겼다가 돌려놓기 위해 필요한 최소 전기료를 $Q$개의 줄에 순서대로 출력한다.