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>
#define llong long long
#define mkpr make_pair
#define riterator reverse_iterator
#define y1 Lorem_ipsum_dolor
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int mxN = 1<<17;
const int P = 998244353;
const llong Inv2 = 499122177ll;
const llong W = 716070898ll;
int sg[mxN+3];
llong pwW[mxN+3];
llong f[3][mxN+3],g[mxN+3];
vector<int> adj[mxN+3]; vector<int> vec;
int n,m,dgr;

int get_mex()
{
	int ret = 0; sort(vec.begin(),vec.end());
	for(int i=0; i<vec.size(); i++)
	{
		if(vec[i]==ret) {ret++;}
		else if(vec[i]>ret) {break;}
	}
	vec.clear(); return ret;
}

void fwt(int dgr,int coe,llong poly[],llong ret[])
{
	for(int i=0; i<(1<<dgr); i++) ret[i] = poly[i];
	for(int i=1; i<(1<<dgr); i<<=1)
	{
		for(int j=0; j<(1<<dgr); j+=(i<<1))
		{
			for(int k=0; k<i; k++)
			{
				llong x = ret[j+k],y = ret[j+i+k];
				ret[j+k] = (x+y)%P,ret[j+i+k] = (x-y+P)%P;
				if(coe==-1) {ret[j+k] = ret[j+k]*Inv2%P,ret[j+i+k] = ret[j+i+k]*Inv2%P;}
			}
		}
	}
}

int main()
{
	scanf("%d",&n); while((1<<dgr)<=n) dgr++;
	pwW[0] = 1ll; for(int i=1; i<=n; i++) pwW[i] = pwW[i-1]*W%P;
	for(int T=0; T<3; T++)
	{
		scanf("%d",&m);
		for(int i=1; i<=m; i++)
		{
			int u,v; scanf("%d%d",&u,&v);
			if(u>v) {swap(u,v);} adj[u].push_back(v);
		}
		for(int i=n; i>=1; i--)
		{
			for(int o=0; o<adj[i].size(); o++)
			{
				vec.push_back(sg[adj[i][o]]);
			}
			sg[i] = get_mex();
//			printf("sg[%d]=%d\n",i,sg[i]);
			f[T][sg[i]] = (f[T][sg[i]]+pwW[i])%P;
		}
		for(int i=1; i<=n; i++) adj[i].clear(),sg[i] = 0;
		fwt(dgr,1,f[T],f[T]);
	}
	for(int i=0; i<(1<<dgr); i++) {g[i] = f[0][i]*f[1][i]%P*f[2][i]%P;}
	fwt(dgr,-1,g,g);
	printf("%lld\n",g[0]);
	return 0;
}