Given the equation:

$$X_1+X_2+\dots+X_n=m$$

We have some constraints on the first $1..n_1$ variables: $X_1 \le A_1$ $X_2 \le A_2$ $\dots$ $X_{n_1} \le A_{n_1}$

We have some constraints on the $n_1+1..n_1+n_2$ variables: $X_{n_1+1} \ge A_{n_1+1}$ $X_{n_1+2} \ge A_{n_1+2}$ $\dots$ $X_{n_1+n_2} \ge A_{n_1+n_2}$

Find the number of positive integer solutions to this equation under these constraints. The answer may be very large, so please output the answer modulo $p$, i.e., the remainder of the answer divided by $p$.

Input

The input contains multiple test cases. The first line contains two positive integers $T$ and $p$. $T$ represents the number of data sets in this test point, and the meaning of $p$ is as described in the problem statement.

For each data set, the first line contains four non-negative integers $n, n_1, n_2, m$. The second line contains $n_1+n_2$ positive integers, representing $A_1..A_{n_1+n_2}$. Please note that if $n_1+n_2$ equals $0$, this line will be an empty line.

Output

There are $T$ lines in total, each containing a positive integer representing the answer after modulo $p$.

Examples

Input 1

3 10007
3 1 1 6
3 3
3 0 0 5
3 1 1 3
3 3

Output 1

3
6
0

Note

For the first data set, the three solutions are $(1,3,2), (1,4,1), (2,3,1)$. For the second data set, the six solutions are $(1,1,3), (1,2,2), (1,3,1), (2,1,2), (2,2,1), (3,1,1)$.

Constraints

For 100% of the test data: $T \le 5$, $1 \le A_{1..n_1+n_2} \le m$, $n_1+n_2 \le n$.