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ẽ.
![enter image description here][1]
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)\).

Input

• Dòng đầu tiên ghi \(4\) số nguyên \(m, n, k\) và $Q\ (1