왕의 무도회

예로부터 바이토시아의 통치자들은 모두 성대한 무도회를 열곤 했고, 바이투르 왕도 예외가 아니다. 그러나 무도회를 열 때마다 무언가 부족하다고 느꼈다. 그래서 다음 무도회에 예술과 서커스 요소를 더해 분위기를 살리기로 했다.

그는 수석 고문에게 공연 안무를 맡겼고, 고문은 오래 걸리지 않아 자신의 구상을 왕에게 보고했다.

고문의 계획에 따르면 $n^2$명의 서커스 단원이 공연에 참여한다. 여기서 $n$은 자연수다. 피날레에서 단원들은 $n$개의 행에 서며, 각 행에는 정확히 $n$명이 선다. 그렇게 한 변의 길이가 $n$인 $n \times n$ 정사각형 대형이 만들어진다. 피날레가 시작될 때 각 단원은 불타는 훌라후프를 들고 춤추거나, 아무것도 들지 않고 춤춘다. 자정이 되는 순간, 지금까지 훌라후프를 들고 있던 일부 단원이 훌라후프가 없던 다른 단원에게 그것을 던질 수 있다. 한 단원에게는 최대 한 명만 훌라후프를 던질 수 있다.

모든 단원은 같은 순간에 던진다. 전문가들이라 공중에서 훌라후프끼리 부딪치는 일은 없다. 다만 조건이 하나 있다. 각 던지기는 같은 행이나 같은 열에 선 단원 사이에서만 이루어져야 한다.

바이투르 왕은 큰 규모를 좋아하므로 단원 수가 매우 많을 수 있다. 고문은 계획을 세울 때 먼저 $n$을 정하고, 모든 단원이 훌라후프 없이 피날레를 시작한다고 가정했다. 그다음 $m$번에 걸쳐 행의 구간과 열의 구간을 골라 직사각형을 정했다. 그 안의 단원은 이전 계획과 반대로 시작해야 한다. 즉 훌라후프를 들고 시작하기로 했던 단원은 빈손으로, 빈손으로 시작하기로 했던 단원은 훌라후프를 들고 시작한다.

구상을 본 바이투르 왕은 공연을 최대한 화려하게 하려면 훌라후프를 던지는 횟수가 최대한 많아야 한다는 사실을 곧바로 깨달았다. 그는 그 횟수를 알고 싶어 했지만, 계속 계획을 수정하고 있어 쉽지 않다. 지금까지 이루어진 수정은 $q$번이다. 각 수정은 단원 한 명을 골라 그가 피날레를 시작하는 방식을 바꾼다. 훌라후프를 들고 시작했다면 빈손으로, 빈손이었다면 들고 시작하게 한다. 왕의 수정은 계획에 계속 남는다. 어떤 단원이 수정 대상이 되었다면, 왕이 다시 그 단원을 고르기 전까지 효과가 이어진다.

고문을 도와 $[0, q]$에 속한 모든 정수 $i$에 대해, 고문의 원래 계획과 왕의 처음 $i$번의 수정을 반영한 뒤 가능한 던지기 횟수의 최댓값을 구하라.

첫 줄에 정수 $n$, $m$, $q$가 주어진다 ($1 \le n \le 300000$, $0 \le m, q \le 300000$).

다음 $m$개의 줄에는 각각 정수 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다 ($1 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le n$). 이는 행 번호 $x_1$부터 $x_2$까지, 열 번호 $y_1$부터 $y_2$까지(양 끝 포함) 모든 단원에게 변경이 적용되었다는 뜻이다. 행과 열은 모두 1부터 $n$까지 번호가 매겨져 있다.

다음 $q$개의 줄에는 각각 정수 $a_i$, $b_i$가 주어진다 ($1 \le a_i, b_i \le n$). 이는 $i$번째 왕의 수정이 행 번호 $a_i$, 열 번호 $b_i$에 있는 단원에게 적용되었다는 뜻이다.

$q + 1$개의 줄을 출력한다. $i$번째 줄에는 왕의 수정 $i-1$번을 반영한 뒤 가능한 던지기 횟수의 최댓값을 적는다.

첫 번째 예제에 대한 설명이다. 아래 그림은 왕의 첫 번째 수정 이후의 상황이다. 피날레를 훌라후프를 들고 시작하는 단원은 굵은 원으로 표시했다. 화살표는 가능한 던지기 순서 중 하나를 보여준다.