Kunai là một loại vũ khí sắc nhọn của ninja có hình dáng giống dao. Có \(N\) ninja đứng trên một lưới ô vuông gồm \(W\) cột và \(H\) hàng. Mỗi ninja đứng tại tâm một ô và không có hai ninja đứng cùng ô. Mỗi người cầm một kunai và nhìn theo một trong bốn hướng: lên, xuống, trái hoặc phải. Tại thời điểm \(0\), tất cả ninja đồng thời ném kunai theo hướng mình đang nhìn.

Mỗi kunai bay thẳng với vận tốc \(1\). Nếu từ hai kunai trở lên đến cùng một vị trí tại cùng một thời điểm, tất cả chúng va chạm và biến mất. Có thể bỏ qua kích thước của kunai. Kunai tiếp tục bay theo hướng ban đầu với vận tốc không đổi cho tới khi va chạm.

Trong ba hình sau, mũi tên biểu diễn kunai và hướng bay. Mọi mũi tên nét đậm trong từng hình đều va chạm với nhau.

{{asset:apio12-kunai-collision-1}}

{{asset:apio12-kunai-collision-2}}

{{asset:apio12-kunai-collision-3}}

Ngược lại, trong mỗi hình dưới đây, các mũi tên nét đậm không va chạm với nhau. Ở hình thứ hai và thứ ba, mũi tên nét mảnh va chạm với một mũi tên nét đậm trước; vì kunai đã va chạm sẽ biến mất, hai mũi tên nét đậm không còn có thể va chạm.

{{asset:apio12-kunai-no-collision-1}}

{{asset:apio12-kunai-no-collision-2}}

{{asset:apio12-kunai-no-collision-3}}

Hãy đếm số ô của lưới \(W\times H\) mà ít nhất một kunai đi qua sau khi đã chờ đủ lâu.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(W,H\).
• Dòng thứ hai chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(X_i,Y_i,D_i\). Ninja \(i\) đứng ở cột thứ \(X_i\) tính từ trái sang và hàng thứ \(Y_i\) tính từ trên xuống. Không có hai ninja cùng vị trí.

Hướng được mã hóa như sau:

• \(D_i=0\): sang phải.
• \(D_i=1\): lên trên.
• \(D_i=2\): sang trái.
• \(D_i=3\): xuống dưới.

Dữ liệu ra

In số ô mà ít nhất một kunai đi qua.

Ràng buộc

• \(1\le N\le100\,000\).
• \(1\le W,H\le1\,000\,000\,000\).
• \(1\le X_i\le W\) và \(1\le Y_i\le H\).

Ví dụ

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

11

7 6
12
3 2 3
6 3 2
7 1 3
1 5 0
3 6 1
6 6 1
4 5 2
1 3 0
6 5 2
5 1 2
6 4 3
4 1 3

29

Giải thích

Trạng thái ví dụ thứ nhất tại thời điểm \(0\):

{{asset:apio12-kunai-sample-start}}

Tại thời điểm \(0.5\), kunai \(2\) và \(3\) va chạm rồi biến mất. Hình dưới là trạng thái tại thời điểm \(1\); các ô màu xám là những ô kunai đã đi qua.

{{asset:apio12-kunai-sample-t1}}

Tại thời điểm \(2\), kunai \(1\) và \(5\) va chạm rồi biến mất.

{{asset:apio12-kunai-sample-t2}}

Sau thời điểm \(2\) không còn va chạm nào trong lưới. Cuối cùng có \(11\) ô được kunai đi qua.

{{asset:apio12-kunai-sample-final}}

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2012, bài Kunai.