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ẽ.

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 yi < 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~) cho trước đến ô (~m~, ~n~) cho ~10^9~.

Dữ liệu mẫu 1

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

Kết quả mẫu 1

1
1
0

Dữ liệu mẫu 2

4 5 0 2
1 2
3 3

Kết quả mẫu 2

2
1

Ràng buộc:

• 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.