별이 빛나는 밤 (Hard)

본 문제와 Easy 문제는 입력 제한만 다를 뿐 같은 문제이다.

스타는 밖에서 밤하늘 사진을 찍고 있다. 그중 가장 잘 찍힌 사진을 액자에 담아 전시하려고 한다. 스타는 사진마다 다음 방법으로 점수를 매기려고 한다.

밤하늘은 2차원 격자로 나타낼 수 있으며, 각 칸은 $(x, y)$로 표현한다. 사진에 담긴 밤하늘 영역은 항상 직사각형이고, 격자 칸의 일부만 사진에 포함되는 경우는 없다.

위치가 $(x_i, y_i)$, 밝기가 $p_i$인 별 $N$개가 있을 때, 격자 칸 $(x, y)$의 밝기 $b_{x, y}$는 다음과 같이 계산한다.

$b_{x, y} = \sum_{i = 1}^N \max(p_i-(|x-x_i|+|y-y_i|), 0)$

사진의 맨 왼쪽 아래 칸이 $(a, b)$, 맨 오른쪽 위 칸이 $(c, d)$일 때, 사진의 점수 $score$는 다음과 같이 계산한다.

$score=\sum_{y = b}^d \sum_{x = a}^c b_{x, y}$

사진을 찍을 당시 밤하늘에 떠 있던 별 $N$개의 정보와 사진 정보가 주어질 때, 사진의 점수를 구한다.

첫째 줄에 별의 개수 $N$이 주어진다. ($1 \leq N \leq 500\,000$)

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번째 별의 위치 $x_i$, $y_i$와 밝기 $p_i$가 주어진다. 같은 칸에 별이 두 개 이상 놓이는 경우는 없다. ($-10\,000 \leq x_i \leq 10\,000$, $-10\,000 \leq y_i \leq 10\,000$, $1 \leq p_i \leq 10\,000$)

마지막 줄에는 사진 정보 $a$, $b$, $c$, $d$가 주어진다. 사진의 맨 왼쪽 아래 칸이 $(a, b)$, 맨 오른쪽 위 칸이 $(c, d)$이다. ($-10\,000 \leq a \leq c \leq 10\,000$, $-10\,000 \leq b \leq d \leq 10\,000$, $c-a \leq 10\,000$, $d-b \leq 10\,000$)

입력으로 주어지는 모든 수는 정수이다.

사진의 점수를 출력한다.