Problem: Given are simple undirected graphs X, Y, Z, with N vertices each and M_1, M_2, M_3 edges, respectively. The vertices in X, Y, Z are respectively called x_1, x_2, \dots, x_N, y_1, y_2, \dots, y_N, z_1, z_2, \dots, z_N. The edges in X, Y, Z are respectively (x_{a_i}, x_{b_i}), (y_{c_i}, y_{d_i}), (z_{e_i}, z_{f_i}).

Based on X, Y, Z, we will build another undirected graph W with N^3 vertices. There are N^3 ways to choose a vertex from each of the graphs X, Y, Z. Each of these choices corresponds to the vertices in W one-to-one. Let (x_i, y_j, z_k) denote the vertex in W corresponding to the choice of x_i, y_j, z_k.

We will span edges in W as follows:

* For each edge (x_u, x_v) in X and each w, l, span an edge between (x_u, y_w, z_l) and (x_v, y_w, z_l).
* For each edge (y_u, y_v) in Y and each w, l, span an edge between (x_w, y_u, z_l) and (x_w, y_v, z_l).
* For each edge (z_u, z_v) in Z and each w, l, span an edge between (x_w, y_l, z_u) and (x_w, y_l, z_v).



Then, let the weight of the vertex (x_i, y_j, z_k) in W be 1,000,000,000,000,000,000^{(i +j + k)} = 10^{18(i + j + k)}. Find the maximum possible total weight of the vertices in an independent set in W, and print that total weight modulo 998,244,353.

Constraints

* 2 \leq N \leq 100,000
* 1 \leq M_1, M_2, M_3 \leq 100,000
* 1 \leq a_i, b_i, c_i, d_i, e_i, f_i \leq N
* X, Y, and Z are simple, that is, they have no self-loops and no multiple edges.

Input

Input is given from Standard Input in the following format:


N
M_1
a_1 b_1
a_2 b_2
\vdots
a_{M_1} b_{M_1}
M_2
c_1 d_1
c_2 d_2
\vdots
c_{M_2} d_{M_2}
M_3
e_1 f_1
e_2 f_2
\vdots
e_{M_3} f_{M_3}


Output

Print the maximum possible total weight of an independent set in W, modulo 998,244,353.

Examples

Input

2
1
1 2
1
1 2
1
1 2


Output

46494701


Input

3
3
1 3
1 2
3 2
2
2 1
2 3
1
2 1


Output

883188316


Input

100000
1
1 2
1
99999 100000
1
1 100000


Output

318525248

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int MM = 500;
const int MN = 100100;
const ll M = 998244353;
bitset<MM> bs[MM][2];
int pt[MM][2];
int get(int a, int b) {
	int st = max(pt[a][0],pt[b][1]);
	while(bs[a][0][st] || bs[b][1][st]) {
		st++;
	}
	return st;
}
void up(int a, int b, int val) {
	bs[a][0].set(val);
	bs[b][1].set(val);
	while(bs[a][0][pt[a][0]]) {pt[a][0]++;}
	while(bs[b][1][pt[b][1]]) {pt[b][1]++;}
}
ll mul(ll a, ll b) {
	return (a*b)%M;
}
ll bp(ll b, ll p) {
	ll ac = 1;
	while(p) {
		if(p&1) {ac = mul(ac,b);}
		b = mul(b,b);
		p >>= 1;
	}
	return ac;
}
ll wor[MM][3];
vvi g[3];
int ro[3];
ll po[MN];
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	memset(pt,0,sizeof(pt));
	memset(wor,0,sizeof(wor));
	int n;
	cin >> n;
	po[0] = 1;
	ll B = bp(10,18);
	for(int i=1;i<MN;i++) {
		po[i] = mul(po[i-1],B);
	}
	for(int i=0;i<3;i++) {
		g[i].assign(n,vi());
		int m;
		cin >> m;
		for(int j=0;j<m;j++) {
			int a,b;
			cin >> a >> b;a--;b--;
			if(a < b) {swap(a,b);}
			g[i][a].push_back(b);
		}
		int ctr = 0;
		vi cu,nu;
		for(int j=0;j<n;j++) {
			cu.push_back(j);
		}
		bitset<MN> ko;
		while(!cu.empty()) {
			ko.reset();
			nu.clear();
			for(int j=cu.size()-1;j>=0;j--) {
				int u = cu[j];
				if(ko[u]) {
					nu.push_back(u);continue;}
				wor[ctr][i] += po[u+1];
				if(wor[ctr][i] >= M) {wor[ctr][i] -= M;}
				for(int k=0;k<g[i][u].size();k++) {
					ko.set(g[i][u][k]);
				}
			}
			ctr++;
			cu = nu;
			reverse(cu.begin(),cu.end());
		}
		ro[i] = ctr;
	}
	ll res = 0;
	for(int i=0;i<ro[0];i++) {
		for(int j=0;j<ro[1];j++) {
			int re = get(i,j);
			if(re < ro[2]) {
				res += mul(wor[i][0],mul(wor[j][1],wor[re][2]));
				up(i,j,re);
			}
		}
	}
	res %= M;
	cout << res << '\n';
}