다트게임

승규와 의석이는 다트게임을 즐긴다. 다트게임은 $N \times M$ 크기의 격자 모양 다트판에서 진행되며, 두 사람이 던지는 다트는 항상 다트판에 꽂힌다. 다트판은 $1 \times 1$ 크기의 정사각형 칸 $N \times M$개로 나뉘어 있다. 각 칸은 $(x, y)$로 나타내며, $x$는 위에서 몇 번째 칸인지, $y$는 왼쪽에서 몇 번째 칸인지를 뜻한다. $x$와 $y$는 1부터 시작한다. 한 라운드는 다음과 같이 진행되며, 두 사람은 총 $K$ 라운드를 진행한다. ($R$은 $R$번째 라운드를 뜻한다.)

1. 승규가 다트를 던진다. 승규가 던진 다트는 $(A_R, B_R)$에 꽂히고 $X_R$의 가중치를 가진다.
2. 의석이가 다트를 던진다. 던진 다트는 $(C_R, D_R)$에 꽂힌다.
3. 의석이가 점수를 얻는다.

의석이가 얻는 점수는 다음과 같이 계산한다.

• $f(i,j)=(A_i - C_j)^2 + (B_i - D_j)^2$일 때,
• $R$라운드에서 의석이가 얻는 점수는 $(\sum_{i=1}^R{(f(i,R) \times X_i)})$이다.

게임이 끝난 뒤 승규가 화장실에 간 틈을 타 의석이는 점수를 조작하려고 한다. 의석이는 자신이 던진 다트 중 최대 $L$개의 좌표를 바꿀 수 있다. 좌표가 바뀐 다트도 다트판 위에 있어야 한다. 의석이는 자신이 얻는 원래 점수, 조작해서 얻을 수 있는 최대 점수, 조작해서 얻을 수 있는 최소 점수를 알고 싶어 한다.

예를 들어 위와 같은 상황을 보자. 붉은색 다트는 승규가 던진 다트이고, 검은색 다트는 의석이가 던진 다트이다. 다트에 적힌 숫자는 다트를 던진 라운드를 뜻한다. (가중치는 모두 1로 같다.) 이 상황에서 1라운드에 의석이가 얻는 점수는 1점이고, 2라운드에 얻는 점수는 3점이다. 즉 의석이가 원래 얻는 총점은 4점이다. 여기서 의석이가 자신의 2라운드 다트를 (3,3)으로 옮기면 얻을 수 있는 최대 총점인 14점을 얻는다. 또는 2라운드 다트를 (1,1)로 옮기면 얻을 수 있는 최소 총점인 2점을 얻는다.

계산을 손가락으로밖에 못 하는 의석이를 위해 대신 계산을 해 주자. 의석이가 얻는 원래 점수, 조작해서 얻을 수 있는 최대 점수, 조작해서 얻을 수 있는 최소 점수를 구하자. 값이 너무 커질 수 있으므로 1,000,000,007로 나눈 나머지를 구한다.

첫째 줄에 양의 정수 $N, M, K, L$이 빈 칸을 사이에 두고 주어진다. $N$은 다트판의 세로 크기, $M$은 다트판의 가로 크기, $K$는 진행할 라운드 수, $L$은 바꿀 수 있는 다트의 수다. 둘째 줄부터 $K$개의 줄에 걸쳐 라운드 순서대로 각 줄에 라운드 정보인 양의 정수 $A_R, B_R, X_R, C_R, D_R$이 빈 칸을 사이에 두고 주어진다.

의석이의 원래 점수, 조작해서 얻을 수 있는 최대 점수, 조작해서 얻을 수 있는 최소 점수를 각각 한 줄에 하나씩 출력한다. 출력할 때에는 1,000,000,007로 나눈 나머지를 출력해야 한다.

• 1 ≤ $N, M$ ≤ 105
• 1 ≤ $K$ ≤ $\min(N \times M , 4 \times 10^5)$
• 1 ≤ $L$ ≤ $K$
• 1 ≤ $A_R, C_R$ ≤ $N$
• 1 ≤ $B_R, D_R$ ≤ $M$
• 1 ≤ $X_R$ ≤ 103