#include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int64_t N; int M, B, Q; cin >> N >> M >> B >> Q; using atcoder::modint; modint::set_mod(B); vector> edges(M); for (auto& [i, j] : edges) { cin >> i >> j; } vector U; for (auto [i, j] : edges) { U.push_back(i); U.push_back(j); } ranges::sort(U); U.resize(size(ranges::unique(U))); atcoder::dsu d(size(U)); modint all = 1; for (auto [i, j] : edges) { auto ti = ranges::lower_bound(U, i) - begin(U); auto tj = ranges::lower_bound(U, i) - begin(U); if (d.same(i, j)) { all *= 2; } else { d.merge(i, j); } } vector> v; while (Q--) { bitset<400> cur; for (int _ = 3; _--;) { int i; cin >> i; cur[i] = 1; } for (const auto& e : v) { auto pos = e._Find_first(); if (cur[pos]) { cur ^= e; } } if (cur.any()) { v.push_back(cur); } } auto ans = modint(2).pow(size(v)); cout << (all - ans).val() << ' ' << ans.val() << '\n'; }