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 ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
#define pb push_back
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int inf = 1e18 ; 
const int P = 998244353 ; 
const int N = 1e5 + 5 ; 
const int M = 1e5 + 5 ;
int n, m1, m2, m3, ans[N], h[N], f[N], g[N], f1[N], f2[N], f3[N], Ans ;
int book[N] ; 
vector<int> G1[N], G2[N], G3[N] ; 
signed main()
{
	n = gi(), ans[1] = inf % P ; 
	rep( i, 2, n ) ans[i] = ans[i - 1] * ans[1] % P ; 
	
	int x, y ; m1 = gi() ; 
	rep( i, 1, m1 ) x = gi(), y = gi(), ( x < y ) ? G1[x].pb(y) : G1[y].pb(x) ;
	m2 = gi() ; 
	rep( i, 1, m2 ) x = gi(), y = gi(), ( x < y ) ? G2[x].pb(y) : G2[y].pb(x) ;
	m3 = gi() ; 
	rep( i, 1, m3 ) x = gi(), y = gi(), ( x < y ) ? G3[x].pb(y) : G3[y].pb(x) ;
	
	for( re int i = n, l; i >= 1; -- i ) {
		for( int j : G1[i] ) book[f1[j]] = 1 ; l = 0 ;
		while( book[l] ) ++ l ; f1[i] = l ;
		for( int j : G1[i] ) book[f1[j]] = 0 ; 
		
		for( int j : G2[i] ) book[f2[j]] = 1 ; l = 0 ;
		while( book[l] ) ++ l ; f2[i] = l ;
		for( int j : G2[i] ) book[f2[j]] = 0 ; 
		
		for( int j : G3[i] ) book[f3[j]] = 1 ; l = 0 ;
		while( book[l] ) ++ l ; f3[i] = l ;
		for( int j : G3[i] ) book[f3[j]] = 0 ; 
		f[f1[i]] = ( f[f1[i]] + ans[i] ) % P, 
		g[f2[i]] = ( g[f2[i]] + ans[i] ) % P,
		h[f3[i]] = ( h[f3[i]] + ans[i] ) % P ; 
	}
	rep( i, 0, 500 ) rep( j, 0, 500 ) rep( k, 0, 500 ) 
	( ( i ^ j ^ k ) == 0 ) ? Ans = ( Ans + f[i] * g[j] % P * h[k] % P ) % P : Ans = Ans ; 
	
	cout << Ans << endl ; 
	return 0 ; 
}