다트게임

승규와 의석이는 다트게임을 즐겨한다. 다트게임은 $N \times M$ 형태의 격자모양 다트판에서 이뤄지며 승규와 의석이가 던지는 다트는 항상 다트판에 꽂힌다. 다트판은 1×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