Số cách đi quân

Xét một bàn cờ vua kích thước \(m \times n\) gồm \(m\) dòng và \(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ã đang ở ô \((x, y)\) có thể di chuyển đến một trong bốn ô sau (nếu vẫn nằm trong bàn cờ):

• \((x-1,\, y+2)\)
• \((x+1,\, y+2)\)
• \((x+2,\, y+1)\)
• \((x+2,\, y-1)\)

Trên bàn cờ có \(k\) ô bị cấm, quân mã không được phép đi vào các ô này.

Yêu cầu. Với mỗi truy vấn cho trước ô xuất phát \((x_i, y_i)\), hãy tính số cách di chuyển quân mã từ \((x_i, y_i)\) đến \((m, n)\), không đi vào ô bị cấm.
Vì kết quả có thể rất lớn, chỉ cần in ra phần dư khi chia cho \(10^9\).

Input

• Dòng đầu tiên chứa bốn số nguyên \(m, n, k, Q\) \((1 < m, n \le 1000;\ 0 \le k \le 10;\ 1 \le Q \le 10^5)\).
• \(k\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(kx_i, ky_i\) cho biết ô \((kx_i, ky_i)\) là ô bị cấm \((1 \le kx_i < m;\ 1 \le ky_i < n)\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i, y_i\) \((1 \le x_i < m;\ 1 \le y_i < n)\), là ô xuất phát của một truy vấn.

Output

• Gồm \(Q\) dòng, dòng thứ \(i\) in ra \(W_i\) là số cách đi từ \((x_i, y_i)\) đến \((m, n)\) theo đúng luật di chuyển và tránh ô cấm, lấy modulo \(10^9\).

Scoring

• (30%) \(1 < m, n \le 100\), \(k = 0\), \(Q \le 10^2\);
• (20%) \(1 < m, n \le 100\), \(0 \le k \le 10\), \(Q \le 10^2\);
• (50%) Không có ràng buộc thêm ngoài đề bài.

Input

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

Output

%
1
1
0

Input

%
4 5 0 2
1 2
3 3

Output

%
2
1