Точка n-мерного пространства называется допустимой, если все её координаты целые и лежат в отрезке от 0 до m − 1. Таким образом, существует mⁿ различных допустимых точек. Гиперладья может сделать ход из допустимой точки a в допустимую точку b, если a и b различаются ровно в одной координате. Например, (0,2,1) → (2,2,1) → (2,2,0) → (2,1,0) является последовательностью из трёх ходов в трёхмерном пространстве.

Маршрут длины d из точки t₀ в точку t_d — это последовательность допустимых точек t₀, t₁, …, t_d, такая что для любого i из множества {0, 1, …, d − 1} гиперладья может сделать ход из точки t_i в точку t_i + 1.

Даны целые числа n, m, d, q и допустимые точки t₁, t₂, …, t_q. Требуется вычислить количество различных маршрутов длины d из t_i в t_j для всех пар (i, j), где 1 ≤ i, j ≤ q.

В первой строке через пробел записаны пять целых чисел n (1 ≤ n ≤ 50), m (2 ≤ m ≤ 10⁵), d (0 ≤ d ≤ 10⁹), p (1 ≤ p ≤ 10⁹) и q (2 ≤ q ≤ 50). В следующих q строках записаны координаты точек t_i.

Выведите q строк, по q чисел в каждой. j-е число в i-й строке должно быть равно количеству различных маршрутов длины d из t_i в t_j по модулю p.