보이지 않는 부분

2차원 평면 위에 $n$개의 수직 선분이 있다. 서로 무한히 멀리 떨어진 X축 위의 두 점에 서쪽 관찰자와 동쪽 관찰자가 각각 서 있다.

각 관찰자는 음이 아닌 정수 $p$의 시력을 가지며, 이는 선분을 통과해 볼 수 있게 해 준다. 시력 $p$인 관찰자가 어떤 선분 위의 한 점을 볼 수 있다는 것은, 관찰자와 그 점을 잇는 선분과 교차하는 다른 선분의 개수가 $p$개 이하라는 뜻이다. 어떤 선분의 일부분이 두 관찰자 중 누구에게도 보이지 않으면 그 부분을 보이지 않는다고 한다.

$q$개의 질의가 주어진다. 각 질의는 두 정수로 이루어지며, 각각 서쪽 관찰자와 동쪽 관찰자의 시력이다. 각 질의마다 모든 선분에서 보이지 않는 부분의 길이의 합을 구해야 한다.

첫째 줄에 선분의 개수 $n$이 주어진다. ($1 \le n \le 10^5$)

다음 $n$개의 줄 중 $i$번째 줄에는 세 정수 $x_i$, $a_i$, $b_i$가 주어지며, 이는 $i$번째 선분의 위치를 나타낸다. 선분의 양 끝점의 좌표는 각각 $(x_i, a_i)$와 $(x_i, b_i)$이다. ($1 \le x \le 10^9$, $1 \le a_i < b_i \le 10^9$) 모든 선분의 길이는 양수이고, 어떤 두 선분도 공통점을 가지지 않는다.

다음 줄에는 질의의 개수 $q$가 주어진다. ($1 \le q \le 10^5$)

다음 $q$개의 줄에는 각각 두 정수 $l$과 $r$이 주어지며, 이는 그 질의에서 서쪽 관찰자와 동쪽 관찰자의 시력이다. ($0 \le l \le r \le 10^5$)

$q$개의 줄에 각 질의의 답을 한 줄에 하나씩 출력한다.

첫 번째 질의에서 서쪽 관찰자는 첫 번째 선분 전체, 네 번째 선분의 Y좌표 $[5, 6]$ 부분, 여섯 번째 선분의 Y좌표 $[6, 7]$ 부분을 본다.

동쪽 관찰자는 다섯 번째 선분과 여섯 번째 선분 전체, 네 번째 선분의 Y좌표 $[2, 3]$ 부분, 세 번째 선분의 Y좌표 $[1, 2]$ 부분을 본다.

보이지 않고 남는 부분은 두 번째 선분 전체, 세 번째 선분의 Y좌표 $[2, 3]$ 부분, 네 번째 선분의 Y좌표 $[3, 5]$ 부분이다. 이들의 길이의 합은 $1 + 1 + 2 = 4$이다.

다른 모든 질의에서는 보이지 않는 부분이 없다.