А point of n-dimensional space is called valid if all its coordinates are integers between 0 and m − 1, inclusive. Thus, there are mⁿ different valid points. A hyperrook can make a move from valid point a to valid point b if a and b differ in exactly one coordinate. For example, (0,2,1) → (2,2,1) → (2,2,0) → (2,1,0) represents a sequence of three moves in three-dimensional space.

A route of length d from point t₀ to point t_d is a sequence of valid points t₀, t₁, …, t_d such that for any i from {0, 1, …, d − 1} a hyperrook can make a move from point t_i to point t_i + 1.

Given integers n, m, d, q and valid points t₁, t₂, …, t_q you are to find the number of different routes of length d from t_i to t_j for any pair (i, j) where 1 ≤ i, j ≤ q.

The first line contains five space-separated integers n (1 ≤ n ≤ 50), m (2 ≤ m ≤ 10⁵), d (0 ≤ d ≤ 10⁹), p (1 ≤ p ≤ 10⁹) and q (2 ≤ q ≤ 50). Next q lines contain coordinates of points t_i.

Output q lines each containing q space-separated integers. The j-th number in the i-th line should be equal to the number of different routes of length d from t_i to t_j modulo p.