問題文

入力に $4$ 個の正整数 $N, M, B, Q$ と、$N$ 頂点 $M$ 辺を持つ無向多重グラフ $G$ と $Q$ 個のクエリ（後述）が与えられます。

ただしここでの無向多重グラフは自己ループを持たないものを指します。

$G$ の頂点を $N$ 未満の各非負整数 $n$ で番号付け「頂点 $n$」と呼び、$G$ の辺を $M$ 未満の各非負整数 $m$ で番号付け「辺 $m$」と呼び、辺 $m$ の結ぶ $2$ 頂点を頂点 $i_m$ と頂点 $j_m$ （$i_m, j_m$ は $0 \leq i_m < j_m < N$ を満たす整数）と置きます。

$3$ 個の $M$ 未満の非負整数 $m_0, m_1, m_2$ に対し、辺 $m_0$ と辺 $m_1$ と辺 $m_2$ が $3$ 頂点を通る閉路をなすということをここでは $\triangle m_0 m_1 m_2$ と書き表します。

各クエリは、$3$ 個の $M$ 未満の非負整数 $m_0, m_1, m_2$ の組 $(m_0,m_1,m_2)$ であって以下の $2$ 条件を満たすものです：

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

また辺 $m_0$ と辺 $m_1$ と辺 $m_2$ を「三角形 $(m_0,m_1,m_2)$ の $3$ 辺」と呼びます。

塗り分け方は全部で $2^M$ 通りありますが、このうち次の条件を満たす塗り分け方を「良い塗り分け方」と呼びます：

• $N$ 未満の任意の非負整数 $n$ に対し、頂点 $n$ を端点に持つ白い辺の個数は偶数である。

良い塗り分け方の集合 $S$ と $T$ を以下の手続きで定める時、最終的な $S$ と $T$ の要素数を $B$ で割った余りがそれぞれいくつになるか答えてください。

1. まず最初に、$S$ を「少なくとも $1$ 本の辺を白く塗る良い塗り分け方」全体の集合と定め、$T$ を「全ての辺を黒く塗る良い塗り分け方」のみからなる集合と定めます。
2. そしてクエリ $(m_0,m_1,m_2)$ が与えられるたび、次の条件を満たす良い塗り分け方 $c$ であって $S$ に属すものを全て $S$ から削除し $T$ に追加します：
• $T$ に属す良い塗り分け方 $c'$ であって、$c'$ から三角形 $(m_0,m_1,m_2)$ の $3$ 辺の色を全て変更して得られる塗り分け方が $c$ であるものが存在する。

入力

入力は以下の形式で標準入力から与えられます：

• $1$ 行目に $N, M, B, Q$ が半角空白区切りで与えられます。
• $M$ 未満の各非負整数 $m$ に対し、$2 + m$ 行目に $i_m, j_m$ が半角空白区切りで与えられます。
• $Q$ 以下の各正整数 $q$ に対し、$1 + M + q$ 行目に $q$ 個目のクエリの各成分が半角空白区切りで与えられます。

制約

入力は以下の制約を満たします：

• $N$ は $3 \leq N \leq 10^{18}$ を満たす整数
• $M$ は $3 \leq M \leq 4 \times 10^2$ を満たす整数
• $B$ は $2 \leq B \leq 10^9$ を満たす整数
• $Q$ は $1 \leq Q \leq 10^3$ を満たす整数
• $M$ 未満の各非負整数 $m$ に対し、$i_m, j_m$ は $0 \leq i_m < j_m < N$ を満たす整数
• $Q$ 以下の各正整数 $q$ に対し、$q$ 個目のクエリ $(m_0,m_1,m_2)$ の各成分 $m_0, m_1, m_2$ は $0 \leq m_0 < m_1 < m_2 < M$ と $\triangle m_0 m_1 m_2$ を満たす整数

出力

最終的な $S$ と $T$ の要素数を $B$ で割った余りを半角空白区切りで $1$ 行に出力してください。

最後に改行してください。

サンプル

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