ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1746. Hyperrook

Time limit: 1.0 second
Memory limit: 64 MB
А point of n-dimensional space is called valid if all its coordinates are integers between 0 and m − 1, inclusive. Thus, there are mn 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 t0 to point td is a sequence of valid points t0, t1, …, td such that for any i from {0, 1, …, d − 1} a hyperrook can make a move from point ti to point ti + 1.
Given integers n, m, d, q and valid points t1, t2, …, tq you are to find the number of different routes of length d from ti to tj for any pair (ij) where 1 ≤ i, jq.

Input

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

Output

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 ti to tj modulo p.

Samples

inputoutput
2 8 4 10000000 4
3 5
0 5
3 7
0 0
896 720 720 560
720 896 560 720
720 560 896 560
560 720 560 896
3 3 4 10000000 3
0 2 2
1 1 1
1 2 2
90 36 45
36 90 54
45 54 90
Problem Author: Petr Lezhankin
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009