問題
쿠나이(수리 검)은 칼과 비슷하게 생긴 닌자들이 사용하는 정교한 무기이다. 닌자들은 이 칼을 적에게 던져서 적을 공격한다.
H개의 행(row)과 W개의 열(column)의 정사각형으로 이루어진 격자에 N명의 닌자가 있다.
모든 닌자는 정사각형의 중앙에 있으며, 하나의 정사각형에 에는 단 한 명의 닌자만 있을 수 있다.
각 닌자는 쿠나이를 가지고 있으며 네 방향(위, 아래, 좌, 우) 중 한쪽 방향을 바라보고 있다. 초기(시간 0)에,
모든 닌자들은 자신들의 쿠나이를 그가 바라보고 있는 방향으 로 던진다.
모든 쿠나이는 직선방향으로 1의 속도로 나아간다.
동시에 하나보다 많은 쿠나이가 같은 장소에 도달하면, 쿠나이들은 서로 충돌하여 사라진다.
쿠나이의 크기는 너무 작아서 무시할 수 있다. 또 한, 닌자들은 매우 빨리 움직이기 때문에 쿠나이에 맞지 않는다.
쿠나이는 다른 쿠나이와 부딪히지 않는 한 속도가 줄어들지 않고 계속 같은 방향으로 움직인다.
다음의 그림에서, 화살표는 쿠나이를 나타낸다.
화살표의 방향이 쿠나이가 움직이는 방향이다.
다음의 그림에서 굵게 표시한 쿠나이는 충돌하는 것들이다.
반면에, 다음의 각 그림에서는, 굵게 표시한 화살표는 다른 굵은 화살표와 충돌하지 않는다.
두 번째와 세 번째 그림에서 얇은 화살표는 다른 굵은 화살표와 충돌한다. 충돌한 화살표는 사라지기 때문에,
이 그림들에서는 굵은 화살표가 다른 굵은 화살표와 충돌하지 않는다.
<해야 할 일> W×H 격자에서 충분한 시간이 지난 후 쿠나이가 지나간 정사각형의 수를 계산하라.
<제약조건> 1 ≤ N ≤ 100,000 닌자의 수 1 ≤ W ≤ 1,000,000,000, 1 ≤ H ≤ 1,000,000,000 격자의 크기 1 ≤ Xi ≤ W, 1≤ Yi ≤ H 닌자들의 자료
入力
첫 줄에는 격자의 크기를 나타내는 두 정수 W와 H가 하나의 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 닌자의 수를 나타내는 하나의 정수 N이 주어진다. 그 다음 N개의 줄 중에서 i번째 줄은 왼쪽에서부터 Xi번째 열(column)과 위로부터 Yi번째 행(row)에 있는 닌자 i의 위치를 나타내는 세 정수 Xi, Yi, Di 가 주어진다. 같은 위치에는 두 명의 닌자가 있을 수 없다. 닌자 i의 방향은 Di의 값으로 나타낸다. - Di = 0 이면, 닌자 i는 오른쪽을 향하여 보고 있다. - Di = 1 이면, 닌자 i는 위쪽을 향하여 보고 있다. - Di = 2 이면, 닌자 i는 왼쪽을 향하여 보고 있다. - Di = 3 이면, 닌자 i는 아래쪽을 향하여 보고 있다.
出力
W×H 격자에서 충분한 시간이 지난 후 쿠나이가 지나간 정사각형의 수를 출력한다.
例題
5 4
5
3 3 2
3 2 0
4 2 2
5 4 1
1 1 3
11
ログインしないとコードを書けません。