А point of *n*-dimensional space is called *valid* if all its coordinates are integers between 0 and *m* − 1, inclusive. Thus, there are *m*^{n} 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*_{0} to point *t*_{d} is a sequence of valid points *t*_{0}, *t*_{1}, …, *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*_{1}, *t*_{2}, …, *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*.

### Input

The first line contains five space-separated integers *n* (1 ≤ *n* ≤ 50), *m* (2 ≤ *m* ≤ 10^{5}), *d* (0 ≤ *d* ≤ 10^{9}), *p* (1 ≤ *p* ≤ 10^{9}) and *q* (2 ≤ *q* ≤ 50). Next *q* lines contain coordinates of points *t*_{i}.

### 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 *t*_{i} to *t*_{j} modulo *p*.

### Samples

input | output |
---|

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