Problem Statement

The input gives $4$ positive integers $N, M, B, Q$, an undirected multigraph $G$ with $N$ vertices and $M$ edges, and $Q$ queries (described later).

Here, an undirected multigraph refers to one that has no self-loops.

The vertices of $G$ are numbered with the non-negative integers $n$ less than $N$ and called "vertex $n$", and the edges of $G$ are numbered with the non-negative integers $m$ less than $M$ and called "edge $m$". The $2$ vertices connected by edge $m$ are denoted vertex $i_m$ and vertex $j_m$ ($i_m, j_m$ are integers satisfying $0 \leq i_m < j_m < N$).

For $3$ non-negative integers $m_0, m_1, m_2$ less than $M$, we write $\triangle m_0 m_1 m_2$ to mean that edge $m_0$, edge $m_1$, and edge $m_2$ form a cycle passing through $3$ vertices.

Each query is a tuple $(m_0,m_1,m_2)$ of $3$ non-negative integers $m_0, m_1, m_2$ less than $M$ satisfying the following $2$ conditions:

• $m_0 < m_1 < m_2$
• $\triangle m_0 m_1 m_2$

Also, edge $m_0$, edge $m_1$, and edge $m_2$ are called "the $3$ edges of triangle $(m_0,m_1,m_2)$".

There are $2^M$ ways of painting in total; among them, a way of painting satisfying the following condition is called a "good painting":

• For every non-negative integer $n$ less than $N$, the number of white edges having vertex $n$ as an endpoint is even.

When sets $S$ and $T$ of good paintings are determined by the following procedure, find the remainders when the numbers of elements of the final $S$ and $T$, respectively, are divided by $B$.

1. First, let $S$ be the set of all "good paintings that paint at least $1$ edge white", and let $T$ be the set consisting only of the "good painting that paints all edges black".
2. Then, each time a query $(m_0,m_1,m_2)$ is given, every good painting $c$ belonging to $S$ that satisfies the following condition is removed from $S$ and added to $T$:
• There exists a good painting $c'$ belonging to $T$ such that the painting obtained from $c'$ by changing the colors of all $3$ edges of triangle $(m_0,m_1,m_2)$ is $c$.

Input

The input is given from standard input in the following format:

• On line $1$, $N, M, B, Q$ are given, separated by single spaces.
• For each non-negative integer $m$ less than $M$, $i_m, j_m$ are given on line $2 + m$, separated by single spaces.
• For each positive integer $q$ not exceeding $Q$, the components of the $q$-th query are given on line $1 + M + q$, separated by single spaces.

Constraints

The input satisfies the following constraints:

• $N$ is an integer satisfying $3 \leq N \leq 10^{18}$
• $M$ is an integer satisfying $3 \leq M \leq 4 \times 10^2$
• $B$ is an integer satisfying $2 \leq B \leq 10^9$
• $Q$ is an integer satisfying $1 \leq Q \leq 10^3$
• For each non-negative integer $m$ less than $M$, $i_m, j_m$ are integers satisfying $0 \leq i_m < j_m < N$
• For each positive integer $q$ not exceeding $Q$, the components $m_0, m_1, m_2$ of the $q$-th query $(m_0,m_1,m_2)$ are integers satisfying $0 \leq m_0 < m_1 < m_2 < M$ and $\triangle m_0 m_1 m_2$

Output

Print the remainders when the numbers of elements of the final $S$ and $T$ are divided by $B$, separated by a single space, on $1$ line.

Print a newline at the end.

Sample

3 3 2 1
0 1
1 2
0 2
0 1 2

0 0

3 4 3 1
0 1
0 1
1 2
0 2
0 2 3

2 2

3 4 3 2
0 1
0 1
1 2
0 2
0 2 3
1 2 3

0 1