시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 13 8 6 85.714%

문제

승규와 의석이는 다트게임을 즐겨한다. 다트게임은 $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

예제 입력 1

3 3 2 1
1 1 1 1 2
2 1 1 2 2

예제 출력 1

4
14
2

예제 입력 2

5 5 2 1
4 1 1 1 4
3 1 1 4 2

예제 출력 2

21
63
3

예제 입력 3

5 5 4 2
1 1 6 5 1
1 1 6 4 1
2 1 6 5 3
3 4 7 3 2

예제 출력 3

622
1367
202

예제 입력 4

5 5 6 2
4 1 2 1 4
3 1 3 4 5
1 5 1 4 1
4 2 8 5 1
4 5 5 3 5
4 5 3 3 2

예제 출력 4

488
898
300

예제 입력 5

5 5 20 9
4 1 2 1 4
3 1 3 4 5
1 5 1 4 1
4 2 8 5 1
4 5 5 3 5
4 5 3 3 2
1 1 2 4 3
3 1 4 3 1
3 1 10 4 5
1 1 6 3 2
3 1 8 4 2
1 4 8 4 2
2 4 8 2 2
5 3 6 1 1
5 2 5 1 2
1 4 8 1 3
2 4 6 1 1
3 4 6 1 2
3 5 6 4 4
1 1 7 1 3

예제 출력 5

7344
13562
4514