퍼펙트 사분면

평면 위의 임의의 점 $(x, y)$를 생각하자. 이 점에서 반직선 두 개를 그린다. 하나는 수직으로 아래쪽, 다른 하나는 수평으로 왼쪽 방향이다. 수평 반직선 아래에 있고 수직 반직선 왼쪽에 있는 (무한한) 영역을 사분면이라 하며 $Q(x, y)$로 나타낸다. $Q(x, y)$의 두 반직선이 경계를 이루고, 내부에는 경계가 포함되지 않는다.

$L$을 자연수라 하고, $x, y \in \{0,1,2, \dots , L\}$을 만족하는 평면 위의 점 $(x, y)$들의 집합을 $S$라 하자. 따라서 $S$는 $(L + 1)^2$개의 점으로 이루어진다. 어떤 $k \ge 1$에 대해, 유한 부분집합 $P_1, P_2, \dots , P_k \subseteq S$와 음이 아닌 정수 $c_1, c_2, \dots , c_k$가 주어진다. 모든 $i = 1, 2, \dots , k$에 대해 다음 조건이 성립하면 사분면 $Q$는 $(c_1, c_2, \dots , c_k)$-퍼펙트이다.

$P_i$의 어떤 점도 $Q$의 경계 위에 있지 않고, $|P_i \cap Q| = c_i$이다.

$S$의 점 $(x, y)$ 중 $Q(x, y)$가 $(c_1, c_2, \dots , c_k)$-퍼펙트인 점의 개수를 구하는 프로그램을 작성하라.

입력은 표준 입력에서 읽는다. 첫 줄에는 두 정수 $L$과 $k$가 주어진다 ($1 \le L \le 10^9$, $1 \le k \le 100\,000$). 둘째 줄에는 $k$개의 음이 아닌 정수 $c_1, c_2, \dots , c_k$가 주어진다 ($0 \le c_1, c_2, \dots , c_k \le 1\,000\,000$). 셋째 줄에는 입력 점의 총개수 $N$이 주어진다 ($1 \le N \le 1\,000\,000$). 이는 $N = |P_1| + |P_2| + \cdots + |P_k|$를 뜻한다. 이어지는 $N$개의 줄마다 세 정수 $x$, $y$, $i$가 주어지며 ($0 \le x, y \le L$, $1 \le i \le k$), 점 $(x, y)$가 $P_i$의 원소임을 뜻한다. 축에 평행한 직선 중 $N$개의 입력 점 가운데 두 점을 지나는 직선은 없다고 가정해도 된다.

표준 출력에 한 줄을 출력한다. 이 줄에는 $Q(x, y)$가 $(c_1, c_2, \dots , c_k)$-퍼펙트가 되는 $(x, y) \in S$의 개수를 정수 하나로 적는다.