Circular Cake Cutting with Restrictions

You are given a circular cake with a total of (K \times L) equally spaced cut marks on its circumference. The cake is to be divided among (K) people (numbered from 1 to (K)) as follows:

1. Choose (K) cut marks (each cut may only occur along these marks) so that the cake is divided into (K) pieces. Each piece must consist of exactly (L) consecutive parts of the cake. Here, the cake is divided into (K \times L) parts by its cut marks. More precisely, label the cut marks in clockwise order as (1,2,\dots,K\times L). The region between cut mark (i) and cut mark ((i \bmod (K\times L)) + 1) is called part (i).

2. Distribute the (K) pieces of cake to the (K) people such that every person receives exactly one piece.

In addition, there are (Q) restrictions. The (j)th restriction forces that part (X_j) must be allocated to person (Y_j). It is guaranteed that each part (X_j) appears in at most one restriction.

For each (i=1,2,\ldots, Q), determine the number of valid ways to choose the cut marks and distribute the cake (i.e. assign pieces to people) so that the first (i) restrictions are satisfied. Two ways are considered different if there exists at least one person who receives a different piece.

Output your answer modulo a given prime (P).

Note:

• A cutting is uniquely determined by choosing a starting cut mark (s) (with (1 \le s \le L)). Once (s) is fixed, the cut marks will be (s, s+L, s+2L, \dots, s+(K-1)L) (all arithmetic done modulo (K\times L)).

• For a fixed starting cut (s), the pieces are numbered from (0) to (K-1) where the (j)th piece consists of parts (s+jL, s+jL+1, \dots, s+jL+L-1) (modulo (K \times L)). A restriction (X_j, Y_j) imposes that in the permutation assigning pieces to people, the piece that contains part (X_j) must go to person (Y_j).

• Without any restrictions, there are exactly (L \times K!) valid ways.

inputFormat

The input begins with a line containing four integers: (K), (L), (Q), and (P) (a prime number), where (K) is the number of people, (L) is the number of consecutive parts each piece must have, and (Q) is the number of restrictions.

Then (Q) lines follow. The (j)th of these lines contains two integers (X_j) and (Y_j) indicating that part (X_j) must be assigned to person (Y_j).

Note that the cake has (K \times L) parts labeled from 1 to (K \times L), and it is guaranteed that every (X_j) appears at most once.

outputFormat

Output (Q) lines. The (i)th line should contain a single integer: the number of valid ways (modulo (P)) to divide and assign the cake satisfying the first (i) restrictions.

sample

3 2 2 1000003
1 1
2 2

4
1