Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Trên web đọc dữ liệu từ bàn phím (stdin) và in ra màn hình (stdout).

Nguồn: Olympic truyền thống 30/4 lần XXVII – 2023, Tin học khối 10 – Câu 1 (SOCACH).

Xét một bàn cờ vua có kích thước ~m \times n~ gồm có ~m~ dòng, ~n~ cột. Các dòng được đánh số từ ~1~ đến ~m~, các cột được đánh số từ ~1~ đến ~n~. Một ô nằm trên dòng ~x~, cột ~y~ được kí hiệu là ~(x, y)~.

Một quân mã xuất phát từ một ô trên bàn cờ có thể đi đến một trong bốn ô như hình vẽ.

Hình trong đề: từ ô ~(4, 4)~ quân mã chỉ đi được tới 4 ô ~(3, 6)~, ~(5, 6)~, ~(6, 5)~ và ~(6, 3)~. Tức là từ ô ~(x, y)~ quân mã chỉ đi được tới các ô ~(x-1, y+2)~, ~(x+1, y+2)~, ~(x+2, y+1)~, ~(x+2, y-1)~ (nếu ô đó nằm trong bàn cờ).

Ngoài ra, trên bàn cờ có ~k~ ô mà quân mã không được phép đi vào. Những ô này được gọi là ô bị cấm.

Yêu cầu: Tìm số cách di chuyển của quân mã từ ô ~(x, y)~ cho trước đến ô ~(m, n)~.

Dữ liệu vào

• Dòng đầu tiên ghi 4 số nguyên ~m, n, k~ và ~Q~ ~(1 < m, n \le 1000;\ 0 \le k \le 10;\ Q \le 10^5)~.
• Trên ~k~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~kx_i, ky_i~ cho biết ô ~(kx_i, ky_i)~ bị cấm ~(1 \le kx_i < m;\ 1 \le ky_i < n)~.
• Trên ~Q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~x_i, y_i~ ~(1 \le x_i < m;\ 1 \le y_i < n)~.
• Các số trên một dòng cách nhau bởi ít nhất một khoảng trắng.

Kết quả

• Gồm ~Q~ số nguyên ~W_i~, mỗi số trên một dòng cho biết số cách di chuyển quân mã từ ô ~(x_i, y_i)~ cho trước đến ô ~(m, n)~. Trong đó ~W_i~ là phần dư của phép chia số cách quân mã di chuyển từ ô ~(x_i, y_i)~ đến ô ~(m, n)~ cho ~10^9~.

Giới hạn

• 30% test ứng với 30% số điểm của bài có ~1 < m, n \le 100;\ k = 0;\ Q \le 10^2~.
• 20% test ứng với 20% số điểm của bài có ~1 < m, n \le 100;\ 0 < k \le 10;\ Q \le 10^2~.
• 50% test ứng với 50% số điểm của bài có ràng buộc như đề bài.
• Giới hạn thời gian: 1 giây.

Sample Input 1

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

Sample Output 1

1
1
0

Sample Input 2

4 5 0 2
1 2
3 3

Sample Output 2

2
1

Giải thích

• Ví dụ 1: bàn cờ 4 dòng, 5 cột, ô ~(2, 4)~ bị cấm, đích là ~(4, 5)~. Từ ~(1, 2)~ chỉ có 1 cách: ~(1,2) \to (3,3) \to (4,5)~. Từ ~(3, 3)~ có đúng 1 cách ~(3,3) \to (4,5)~. Ô ~(2, 4)~ bị cấm, quân mã không được đứng ở đó nên đáp án là 0.
• Ví dụ 2: không có ô cấm, nên từ ~(1, 2)~ có thêm đường ~(1,2) \to (2,4) \to (4,5)~, tổng cộng 2 cách; từ ~(3, 3)~ vẫn là 1 cách.