p02737 AtCoder Grand Contest 043 - Giant Graph
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
```python
from collections import defaultdict
import sys

input = lambda: sys.stdin.readline().rstrip()

M = 998244353 # < (1 << 30)

def mod_inv(a, M=M):
  x1, y1, z1 = 1, 0, a
  x2, y2, z2 = 0, 1, M
  while abs(z1) != 1:
    d, m = divmod(z2, z1)
    x1, x2 = x2-d*x1, x1
    y1, y2 = y2-d*y1, y1
    z1, z2 = m, z1
  return x1*z1%M

R_bits = 30
R = 1 << R_bits
R_dec = R - 1
R2 = pow(R, 2, M)
M_neg_inv = mod_inv(-M, R)

def MR(x):
  b = (x * M_neg_inv) & R_dec
  t = x + b * M
  c = t >> R_bits
  d = c - M
  return d if 0 <= d else c

def Montgomery(x):
  return MR(x*R2)

def mex(s):
  for i in range(N+1):
    if i not in s:
      return i

def calc_grundy(edge):
  grundy = [{} for i in range(3)]
  sum_g = [defaultdict(int, {0:M_W_sum}) for i in range(3)]
  M_W = M_W_last
  for i in range(N, 0, -1):
    for g, s, e in zip(grundy, sum_g, edge):
      if i in e:
        m = mex({g.get(j, 0) for j in e[i]})
        if m:
          g[i] = m
          s[g[i]] +=  M_W
          s[0] -=  M_W
    M_W = MR(M_W * M_B_inv)
  return sum_g

def read_edge():
  M = int(input())
  e = defaultdict(list)
  for i in range(M):
    a, b = sorted(map(int, input().split()))
    e[a].append(b)
  return e

N = int(input())
B = pow(10, 18, M)
M_B_inv = Montgomery(mod_inv(B))
M_W_last = Montgomery(pow(B, N, M))
M_W_sum = MR((M_W_last - Montgomery(1)) * MR(Montgomery(B) * Montgomery(mod_inv(B-1))))

edge = [read_edge() for i in range(3)]
sum_g = calc_grundy(edge)
ans = 0
for gx, sx in sum_g[0].items():
  for gy, sy in sum_g[1].items():
    gz = gx^gy
    sz = sum_g[2][gz]
    if sz:
      ans += MR(MR(sx*sy)*sz)
print(MR(ans)%M)

```