Giải bài trực tuyến

Bờm có một cái sân hình chữ nhật có các kích thước là M và N mét. Khu vườn được chia thành M x N ô vuông đơn vị 1 x 1 mét vuông. Các hàng được đánh số liên tục từ 1 đến M, các cột được đánh số liên tục từ 1 đến N. Ô tại hàng i cột j sẽ có tọa độ [i, j].

Sắp đến giáng sinh, Bờm đã trang trí cho cái sân của mình một hệ thống đèn. Hệ thống đèn có thiết kế như sau:

• Bờm làm một hệ thống treo đèn có kích thước M, N và cách mặt sân K + 1 mét.
• Tại tâm của mỗi hình vuông đơn vị, hệ thống treo sẽ cho xuống đất một dây đèn. 
• Trên mỗi dây đèn sẽ gắn đúng K đèn, đèn thứ 1, 2, ..., i, ..., K sẽ lần lượt gắn tại các độ cao 1, 2, ..., i, ..., K mét.
• Đèn nằm trên ô vuông đơn vị có tọa độ [i, j], tại độ cao u sẽ có tọa độ là [u, i, j]ta trong hệ thống đèn.

Bờm cũng đã thiết thế cho mỗi đèn một công tắc. Hệ thống có đến K x M x N công tắc, mỗi lần muốn mở cả hệ thống là phải tốn rất nhiều thời gian. Nên Bờm đã lập trình ra một hệ thống hỗ trợ mở đèn. Các bước sử dụng như sau:

1. Bờm sẽ chọn một số đèn để mở.
2. Sau đó, Bờm mở hệ thống hỗ trợ. Khi hệ trống hỗ trợ được mở, tắc cả các công tắc sẽ bị liệt và không còn sử dụng được nữa (để tránh việc sinh ra các lỗi trong quá trình hệ thống đang chạy). Nhưng bù lại hệ thống hộ trợ sẽ mở thêm một số đèn theo nguyên tắc sau:

• Nếu 2 đèn tại tọa độ [x, y1, z1] và [x, y2, z2] đã mở thì đèn tại [x, y1, z2] và [x, y2, z1] sẽ tự động mở.
• Nếu 2 đèn tại tọa độ [x1, y, z1] và [x2, y, z2] đã mở thì đèn tại [x1, y, z2] và [x2, y, z1] sẽ tự động mở.
• Nếu 2 đèn tại tọa độ [x1, y1, z] và [x2, y2, z] đã mở thì đèn tại [x1, y2, z] và [x2, y1, z] sẽ tự động mở.

Hiện tại Bờm đã mở một số đèn. Bạn hãy mở thêm ít nhất các đèn, để sau khi mở hệ thống hỗ trợ tắc cả đèn đều sáng.

Hình trên mô tả trạng thái các đèn tại cùng độ cao x. Khi 2 đèn vàng [x, y1, z1] và [x, y2, x2] đã mở, thì 2 đèn xanh [x, y1, z2] và [x, y2, z1] sẽ tự mở (sau khi mở hệ thống hỗ trợ).

Input

• Dòng đầu tiên gổm 3 số K, M, N.
• Dòng thứ hai là số đèn đã được Bờm mở trước đó - Q.
• Q dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, i, j (1 ≤ u ≤ K, 1 ≤ i ≤ M, 1 ≤ j ≤ N) - viết cách nhau bởi dấu cách, là tọa độ bóng đèn đã được Bờm mở trước đó. Do không cẩn thận nên có một số đèn được Bờm ghi nhiều hơn 1 lần trong danh sách, mặc dù một đèn chỉ có thể mở một lần (tắc nhiên Bờm sẽ không tắc đèn đã được mở trước đó). Các bạn hãy cẩn thận !!!

Output

• Một dòng duy nhất là kết bài toán - số đèn phải mở thêm ít nhất, để sau khi mở hệ thống hỗ trợ tắc cả các đèn đều sáng.

Giới hạn

• 1 ≤ K, M, N ≤ 1000.
• Q ≤ 1000000.
• 50% số test có K=1.

Example

Input:
2 2 2
1
1 2 2

Output:
2

Giải thích:
- Có đèn [1, 2, 2] đã được Bờm mở trước đó.
- Bạn chỉ cần mở thêm 2 đèn. Sau đó hệ thống hỗ trợ sẽ giúp bạn mở hết các đèn còn lại :
[1, 1, 1] + [2, 2, 2] được mở bằng tay.
--> [1, 2, 1] và [1, 1, 2] tự mở.
--> [2, 1, 1], [2, 1, 2] và [2, 2, 1] tự mở.

Bài này có giá trị là 7 điểm.