The Cutest Predator
The Cutest Predator - Catch an Axolotl in a Bucket
EmeraldBoyGamer đã quá chán với bản Minecraft thông thường, cậu đành lên CurseForge để kiếm thêm mod chơi. Cậu tìm được một bản mod thay đổi khu vực Lush cave (Hang động tươi tốt), Axolotl và các dòng chảy của nước.
Lush cave sau khi thay đổi có dạng lưới \(n\times m\). Các ô đều là nước, nhưng hướng của dòng chảy là khác nhau. Ô thứ i có hướng \(a_{i,j}\), là một trong các giá trị U (lên), D (xuống), L (sang trái), R (sang phải) hoặc . (nước tĩnh). Có \(h\) con Axolotl được spawn ở mỗi khu vực như vậy. Con thứ \(i\) xuất hiện tại ô \((x_i, y_i)\) vào giây \(t_i\). Mỗi giây, nếu đang ở ô có dòng chảy thì nó bị cuốn sang ô kề theo hướng đó. Nếu bị cuốn ra ngoài lưới thì nó trôi mất và không bao giờ bị bắt.
Do dòng nước chảy liên tục và tài nguyên có hạn, cậu chỉ có thể đặt bẫy xô nước bắt Axolotl ở các ô có dòng nước tĩnh. Tất cả Axolotl tới bẫy đều bị bẫy của cậu bắt.
Cho \(q\) truy vấn, truy vấn thứ \(j\) hỏi rằng, tính đến hết giây \(p_j\), cậu đã bắt được bao nhiêu con?
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên \(N, M \ (1\le N, M \le 10^3)\);
- \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) kí tự \(a_{i,j} \ (a_{i,j} \in \{ \)
U,D,L,R,.\( \})\); - Dòng tiếp theo chứa số nguyên \(H \ (1\le H \le 10^5)\);
- \(H\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(x_i, y_i, t_i \ (1\le x_i \le N; 1\le y_i \le M; 0\le t_i \le 10^9)\);
- Dòng tiếp theo chứa số nguyên \(Q \ (1\le Q\le 10^5)\);
- Dòng cuối cùng chứa \(Q\) số nguyên \(p_i \ (0 \le p_i \le 10^9)\).
Kết quả
- In trên \(Q\) dòng, mỗi dòng là một số nguyên tương ứng với kết quả của mỗi truy vấn.
Chấm điểm
- Subtask 1 (40%): \(N \times M, H, Q, t_i, p_i \le 100\).
- Subtask 2 (30%): \(N=1\).
- Subtask 3 (30%): Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
3 4
RRD.
U.DL
UD.L
7
1 1 0
3 4 3
2 4 2
3 3 5
3 2 0
1 4 1
2 2 0
4
0
3
4
100
output
1
2
5
6
Comments