Read problem statements in [Russian], [Bengali], and [Mandarin Chinese] as well.

In a school, there are $C$ clubs (numbered $1$ through $C$) that students can participate in. Each student can be in zero, one or multiple clubs.

Tomorrow, there is a school assembly and $N$ students (numbered $1$ through $N$) will be standing in a line. Each student should wear one of $M$ single-colour shirts provided by the school. The only restriction is that for each club, students in this club must wear shirts with the same colour (possibly the same colour for multiple clubs).

Students in the same clubs try to stand near each other. Formally, for each club $i$, you are given $x_{i}$ segments — let's denote them by $[l_{1},r_{1}],[l_{2},r_{2}], \ldots, [l_{x_{i}},r_{x_{i}}]$, where $1 ≤ l_{1} ≤ r_{1} < l_{2} ≤ r_{2} < \ldots < l_{x_{i}} ≤ r_{x_{i}} ≤ N$ — such for each valid $j$, the students $l_{j}, l_{j}+1, \ldots, r_{j}$ belong to this club.

Determine the number of ways in which the students can choose the colours of their shirts. Two ways to choose colours are considered different if there is at least one student wearing a shirt with a different colour. Since this number can be very large, compute it modulo $998,244,353$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $C$, $N$ and $M$. 
Then, $2C$ lines follow. For each valid $i$, the $(2i-1)$-th of these lines contains a single integer $x_{i}$ and the $2i$-th line contains $2 \cdot x_{i}$ space-separated integers $l_{1},r_{1},l_{2},r_{2}, \ldots, l_{x_{i}},r_{x_{i}}$.

------  Output ------
For each test case, print a single line containing one integer — the number of ways to choose colours modulo $998,244,353$.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N, M ≤ 10^{9}$
$1 ≤ C ≤ 1,000$
$1 ≤ x_{i} ≤ 100$ for each valid $i$

------  Subtasks ------
Subtask #1 (30 points): $N ≤ 1,000$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1

2 6 3

2

1 2 5 6

1

4 6
----- Sample Output 1 ------ 
9
----- explanation 1 ------ 
Example case 1: Students $5$ and $6$ are in both clubs, so these two clubs must wear shirts with the same colour. Student $3$ does not participate in any club and can wear a shirt with any colour out of the three available options.

Difficulty: VERY_HARD
Tags: Number theory

Graph algorithms

Data structures

Mathematics
Skill types: Data structures

Starter code:

Solutions:
from sys import stdin
input = stdin.readline
mod = 998244353

class dsu:

	def __init__(self, n):
		self.p = [0] * (n + 1)
		self.rank = [0] * (n + 1)
		for i in range(1, n + 1):
			self.p[i] = i

	def find(self, node):
		if self.p[node] == node:
			return node
		self.p[node] = self.find(self.p[node])
		return self.p[node]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if self.rank[u] == self.rank[v]:
			self.p[v] = u
			self.rank[u] += 1
		elif self.rank[u] > self.rank[v]:
			self.p[v] = u
		else:
			self.p[u] = v

def answer():
	s = []
	for i in range(1, c + 1):
		x = int(input())
		b = list(map(int, input().split()))
		for j in range(0, 2 * x, 2):
			(l, r) = (b[j], b[j + 1])
			s.append([l, 1, i])
			s.append([r + 1, -1, i])
	s.sort()
	(stack, extra, prev) = ([], 0, 1)
	a = dsu(c)
	for i in range(len(s)):
		if s[i][1] == -1:
			prev = s[i][0]
			stack.pop()
			continue
		if len(stack):
			a.union(stack[-1][2], s[i][2])
		else:
			extra += s[i][0] - prev
			a.union(s[i][2], s[i][2])
		stack.append(s[i])
	extra += n - prev + 1
	comp = set()
	for i in range(1, c + 1):
		comp.add(a.find(i))
	total = len(comp)
	ans = pow(m, total + extra, mod)
	return ans
for T in range(int(input())):
	(c, n, m) = map(int, input().split())
	print(answer())


lii = lambda x: list(map(x, input().split()))
iip = lambda : int(input())
from math import ceil
from collections import defaultdict as df, deque as dq
mod = 998244353

def solve():
	(c, n, m) = lii(int)
	segs = []
	for _ in range(c):
		i = iip()
		intvs = lii(int)
		for i in range(0, len(intvs), 2):
			segs.append([intvs[i], intvs[i + 1], {_}])
	segs.sort()
	st = []
	for seg in segs:
		if not st:
			st.append(seg)
		elif st[-1][1] >= seg[0]:
			st[-1][1] = max(st[-1][1], seg[1])
			st[-1][2] |= seg[2]
		else:
			st.append(seg)
	graph = df(list)
	for seg in st:
		nodes = list(seg[2])
		if nodes == 1:
			for i in nodes:
				if i not in graph:
					graph[i] = []
		else:
			for i in range(1, len(nodes)):
				graph[nodes[i - 1]].append(nodes[i])
				graph[nodes[i]].append(nodes[i - 1])
	vis = [False] * c
	noc = 0
	for i in graph.keys():
		if not vis[i]:
			noc += 1
			queue = dq([i])
			while queue:
				el = queue.popleft()
				vis[el] = True
				for e in graph[el]:
					if not vis[e]:
						queue.append(e)
	students_not_in_any_club = 0
	for i in st:
		students_not_in_any_club += i[1] - i[0] + 1
	students_not_in_any_club = n - students_not_in_any_club
	r = 1
	total_comps = noc + students_not_in_any_club
	while total_comps:
		if total_comps & 1 == 1:
			r = r * m % mod
		total_comps >>= 1
		m = m * m % mod
	print(r)
tc = 1
tc = iip()
for _ in range(tc):
	solve()


mod = 998244353
data = [0 for i in range(1001)]

def unoin(c1, c2):
	p1 = parent(c1)
	p2 = parent(c2)
	if p1 == p2:
		return 0
	data[p2] = p1
	return 1

def parent(club):
	if data[club] == club:
		return club
	return parent(data[club])
for i in range(int(input())):
	(c, n, m) = map(int, input().split())
	data = [j for j in range(c)]
	intervals = []
	end = 0
	for j in range(c):
		x = int(input())
		a = list(map(int, input().split()))
		ind = 0
		for k in range(x):
			intervals.append([a[ind], a[ind + 1], j])
			end = max(end, a[ind + 1])
			ind += 2
	intervals.sort()
	single = intervals[0][0] - 1 + (n - end)
	combined = 0
	prevend = intervals[0][1]
	club = intervals[0][2]
	if len(intervals) > 1:
		for j in intervals[1:]:
			if j[0] <= prevend:
				combined += unoin(club, data[j[2]])
				prevend = max(j[1], prevend)
			else:
				single += j[0] - prevend - 1
				prevend = j[1]
				club = data[j[2]]
	print(pow(m, c - combined + single, mod))


M = 998244353

def find(n):
	if n == parent[n]:
		return n
	parent[n] = find(parent[n])
	return parent[n]

def union(a, b):
	a = find(a)
	b = find(b)
	if a == b:
		return
	else:
		parent[a] = b

def power(a, b):
	if b == 0:
		return 1
	temp = power(a, b // 2)
	temp = temp * temp % M
	if b % 2 == 1:
		temp = temp * a % M
	return temp
for testcase in range(int(input())):
	arr = [int(x) for x in input().split()]
	(c, n, m) = (arr[0], arr[1], arr[2])
	parent = [i for i in range(c)]
	data = []
	for i in range(c):
		z = int(input())
		li = [int(x) for x in input().split()]
		for j in range(0, len(li), 2):
			start = li[j]
			end = li[j + 1]
			arr = [start, end, i]
			data.append(arr)
	data = sorted(data, key=lambda x: x[0])
	rest = 0
	(prevend, prevc) = (data[0][1], data[0][2])
	fn = prevend
	for ele in data[1:]:
		currstart = ele[0]
		currc = ele[2]
		currend = ele[1]
		if currstart <= prevend:
			union(prevc, currc)
			prevend = max(prevend, currend)
		else:
			rest += currstart - prevend - 1
			prevend = currend
			prevc = currc
		fn = max(fn, currend)
	rest += n - fn + (data[0][0] - 1)
	s = set()
	for i in range(c):
		s.add(find(i))
	ans = rest + len(s)
	print(power(m, ans))


from sys import stdin, stdout
input = stdin.readline

def main():
	t = int(input())
	mod = 998244353
	maxn = 10 ** 9 * 2
	sets = list(range(1))
	sizes = [1] * 1

	def get(a):
		if sets[a] != a:
			sets[a] = get(sets[a])
		return sets[a]

	def union(a, b):
		a = get(a)
		b = get(b)
		if a == b:
			return 0
		if sizes[a] > sizes[b]:
			(a, b) = (b, a)
		sets[a] = b
		sizes[b] += sizes[a]
		return 1
	for z in range(t):
		(c, n, m) = map(int, input().split())
		ar = []
		for club in range(c):
			num = int(input())
			xi = list(map(int, input().split()))
			for i in range(0, num * 2, 2):
				ar += [[xi[i], xi[i + 1], club]]
		ar.sort(key=lambda x: x[0] * maxn - x[1])
		n2 = len(ar)
		m2 = n
		i = 0
		n3 = c
		sets = list(range(c))
		sizes = [1] * c
		while i < n2:
			num2 = ar[i][0]
			cl = ar[i][2]
			num = ar[i][1]
			i += 1
			while i < n2 and ar[i][0] <= num:
				num = max(num, ar[i][1])
				n3 -= union(cl, ar[i][2])
				i += 1
			m2 -= num - num2 + 1
		m2 += n3
		print(pow(m, m2, mod))
main()


from sys import stdin
input = stdin.readline

def dfs(curr):
	vis[curr] = 1
	for i in graph[curr]:
		if vis[i] == 0:
			dfs(i)
for _ in range(int(input())):
	(c, n, m) = [int(i) for i in input().split()]
	sinc = [[] for i in range(c)]
	a = []
	for i in range(c):
		xi = int(input())
		pos = [int(i) for i in input().split()]
		for j in range(len(pos)):
			a.append([pos[j], j % 2, i])
	graph = [set() for i in range(c)]
	a.sort()
	first = []
	scnt = []
	ccnt = 0
	for i in a:
		if len(first) == 0:
			first = [i[0], i[2]]
			ccnt += 1
			continue
		if i[1] == 0:
			graph[i[2]].add(first[1])
			graph[first[1]].add(i[2])
			ccnt += 1
		else:
			if ccnt == 1:
				scnt.append(i[0] - first[0] + 1)
				first = []
			ccnt -= 1
	rem = n - sum(scnt)
	vis = [0] * c
	segments = 0
	for i in range(c):
		if vis[i] == 0:
			dfs(i)
			segments += 1
	total = rem + segments
	mod = 998244353
	print(pow(m, total, mod))


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
tc = 1
tc = int(input())
for test in range(1, tc + 1):
	(c, n, m) = inp()
	a = []
	for i in range(c):
		x = int(input())
		b = inp()
		for j in range(0, 2 * x, 2):
			a.append([b[j], b[j + 1], i])
	a.sort(key=lambda x: (x[0], x[1]))
	par = [-1] * c
	rest = 0
	prev = 0
	end = 0
	new = []

	def find(a):
		if par[a] < 0:
			return a
		par[a] = find(par[a])
		return par[a]

	def union(a, b):
		pa = find(a)
		pb = find(b)
		if pa != pb:
			if par[pa] < par[pb]:
				(pa, pb) = (pb, pa)
			par[pa] += par[pb]
			par[pb] = pa
	for i in range(len(a)):
		if a[i][0] > end:
			rest += a[i][0] - end - 1
			new.append([a[i][0], a[i][1]])
			end = a[i][1]
			col = a[i][2]
		else:
			end = max(end, a[i][1])
			new[-1][-1] = end
			union(col, a[i][2])
	rest += n - end
	for i in par:
		if i < 0:
			rest += 1
	print(pow(m, rest, Mod))


p = 998244353

def union(l1, l2):
	(n, m) = (len(l1), len(l2))
	(i, j) = (0, 0)
	merged = []
	while i < n or j < m:
		if i == n:
			x = l2[j]
			j += 1
		elif j == m:
			x = l1[i]
			i += 1
		elif l1[i][0] < l2[j][0]:
			x = l1[i]
			i += 1
		else:
			x = l2[j]
			j += 1
		if not merged or x[0] > merged[-1][1]:
			merged.append(x)
		else:
			merged[-1][1] = max(merged[-1][1], x[1])
	return merged
for _ in range(int(input())):
	(c, n, m) = map(int, input().split())
	res = []
	for i in range(c):
		x = int(input())
		l = list(map(int, input().split()))
		temp = [[l[2 * j], l[2 * j + 1]] for j in range(x)]
		temp.sort(key=lambda x: x[0])
		resr = []
		if not res:
			res.append(temp)
		else:
			for lis in res:
				mer = union(temp, lis)
				if len(mer) == len(temp) + len(lis):
					resr.append(lis)
				else:
					temp = mer
			resr.append(temp)
			res = resr
	print(m ** (n - sum([i[1] - i[0] + 1 for lis in res for i in lis]) + len(res)) % p)


import sys
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 998244353
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def solve():
	for _ in range(ii()):
		(c, n, m) = mi()
		x = []
		par = [i for i in range(c)]

		def find(i):
			if i != par[i]:
				par[i] = find(par[i])
			return par[i]

		def merge(i, j):
			i = find(i)
			j = find(j)
			if i != j:
				if i > j:
					(i, j) = (j, i)
				par[i] = j
		for i in range(c):
			n1 = ii()
			a = li()
			for j in range(0, 2 * n1, 2):
				x.append([a[j], a[j + 1], i])
		if len(x) == 0:
			print(pow(m, n, mod))
			continue
		x.sort()
		mx = x[0][1]
		cnt = x[0][0] - 1
		for i in range(1, len(x)):
			if mx >= x[i][0]:
				merge(x[i][2], x[i - 1][2])
			else:
				cnt += x[i][0] - mx - 1
				cnt %= mod
			mx = max(mx, x[i][1])
		cnt += n - mx
		cnt %= mod
		for i in range(c):
			par[i] = find(par[i])
		cnt += len(set(par))
		cnt %= mod
		print(pow(m, cnt, mod))
solve()


import sys
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def dadd(d, p, val):
	if p in d:
		d[p].append(val)
	else:
		d[p] = [val]

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def prec(a, pre):
	for i in a:
		pre.append(pre[-1] + i)
	pre.pop(0)

def YN(flag):
	print('YES' if flag else 'NO')

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
INF = 10 ** 18
uu = t
mod = 998244353

def find(i):
	if i == a[i]:
		return i
	a[i] = find(a[i])
	return a[i]

def union(x, y):
	(xs, ys) = (find(x), find(y))
	if xs != ys:
		if rank[xs] < rank[ys]:
			(xs, ys) = (ys, xs)
		a[ys] = xs
		rank[xs] += 1
		return False
	return True
while t > 0:
	t -= 1
	(c, n, m) = mi()
	b = []
	a = [i for i in range(c + 1)]
	rank = [0] * (c + 1)
	for i in range(c):
		l = fi()
		w = li()
		for j in range(0, len(w), 2):
			b.append([w[j], 0, i])
			b.append([w[j + 1], 1, i])
	b.sort()
	ans = 1
	lastl = [0] * 2
	lastr = [0] * 2
	ct = 0
	for i in range(len(b)):
		if b[i][1] == 0:
			if ct == 0:
				ans = ans * pow(m, b[i][0] - lastr[0] - 1, mod) % mod
				lastl = [b[i][0], b[i][2]]
			else:
				union(lastl[1], b[i][2])
			ct += 1
		else:
			ct -= 1
			union(lastl[1], b[i][2])
			lastr = [b[i][0], b[i][2]]
	d = {}
	ans = ans * pow(m, n - lastr[0], mod) % mod
	for i in range(c):
		a[i] = find(i)
		inc(d, a[i])
	ans = ans * pow(m, len(d), mod) % mod
	print(ans)


import sys
from functools import partial
from heapq import heapify, heappop, heappush
SAMPLE_IN = 'sample.in'
MODULO = 998244353

def read_int(f) -> int:
	return int(f.readline())

def read_ints(f) -> list:
	return [int(x) for x in f.readline().split()]

def modular_pow(base, exp, modulo):
	res = 1
	base = base % modulo
	if base == 0:
		return 0
	while exp > 0:
		if exp & 1 == 1:
			res = res * base % modulo
		exp = exp >> 1
		base = base * base % modulo
	return res

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		a_copy = a
		while a != self.parent[a]:
			a = self.parent[a]
		while a_copy != a:
			(self.parent[a_copy], a_copy) = (a, self.parent[a_copy])
		return a

	def union(self, a, b):
		(a, b) = (self.find(a), self.find(b))
		if a != b:
			if self.size[a] < self.size[b]:
				(a, b) = (b, a)
			self.num_sets -= 1
			self.parent[b] = a
			self.size[a] += self.size[b]

	def size_of(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def read_case(f=sys.stdin):
	(clubs, students, colors) = read_ints(f)
	segments = []
	for _ in range(clubs):
		f.readline()
		ints = read_ints(f)
		segments.append([ints[i:i + 2] for i in range(0, len(ints), 2)])
	return (students, colors, segments)

def iter_merge(sorted_lists):
	n = len(sorted_lists)
	pointers = [0] * n
	queue = [(elems[0], i) for (i, elems) in enumerate(sorted_lists)]
	heapify(queue)
	while queue:
		(elem, i) = heappop(queue)
		yield (elem, i)
		pointers[i] = j = pointers[i] + 1
		if j < len(sorted_lists[i]):
			heappush(queue, (sorted_lists[i][j], i))

def solve(n_students, n_colors, clubs):
	num_clubs = len(clubs)
	club_sets = UnionFind(num_clubs)
	intervals_iterator = iter_merge(clubs)
	((min_left, curr_right), curr_set) = next(intervals_iterator)
	num_lone_wolves = min_left - 1
	for ((left, right), club_index) in intervals_iterator:
		if left <= curr_right:
			club_sets.union(curr_set, club_index)
		else:
			num_lone_wolves += left - curr_right - 1
		if right > curr_right:
			curr_right = right
			curr_set = club_index
	num_lone_wolves += n_students - curr_right
	num_slots = len(club_sets) + num_lone_wolves
	return modular_pow(n_colors, num_slots, MODULO)

def make_submission(fin=sys.stdin, fout=sys.stdout):
	output = partial(print, file=fout)
	n_cases = int(fin.readline())
	for t in range(1, n_cases + 1):
		case = read_case(fin)
		answer = solve(*case)
		output(answer)
import os
if os.getenv('GCJ_LOCAL'):
	with open(SAMPLE_IN) as s:
		make_submission(s)
else:
	make_submission()


class DisjointSetNode:

	def __init__(self):
		self.parent = self
		self.size = 1
		self.rank = 0

class DisjointSet:

	def __init__(self, n):
		self.arr = []
		for _ in range(n):
			self.arr.append(DisjointSetNode())

	def findParent(self, n):
		p = self.arr[n]
		while p.parent != p:
			p = p.parent
		self.arr[n].parent = p
		return p

	def union(self, a, b):
		(p1, p2) = (self.findParent(a), self.findParent(b))
		if p1 == p2:
			return False
		if p1.rank >= p2.rank:
			p2.parent = p1
			p1.rank += 1 if p1.rank == p2.rank else 0
			p1.size += p2.size
		else:
			p1.parent = p2
			p2.size += p1.size
mod = 998244353
for _ in range(int(input())):
	(c, n, m) = map(int, input().split())
	d = DisjointSet(c)
	club = 1
	t = {}
	for _ in range(c):
		x = int(input())
		temp = list(map(int, input().split()))
		for i in range(0, 2 * x, 2):
			(a, b) = (temp[i], temp[i + 1])
			t[a] = t.get(a, [])
			t[b + 1] = t.get(b + 1, [])
			t[a].append(club)
			t[b + 1].append(-club)
		club += 1
	s = set()
	l = sorted(list(t))
	non = 0
	prev = 1
	for i in l:
		if len(s) == 0:
			non += i - prev
		prev = i
		for cno in t[i]:
			if cno < 0:
				s.remove(-cno)
		for cno in t[i]:
			if cno > 0:
				for cno2 in s:
					d.union(cno - 1, cno2 - 1)
					break
				s.add(cno)
	non += n + 1 - prev
	totalClubs = 0
	for node in d.arr:
		if node == node.parent:
			totalClubs += 1
	z = m
	ans = 1
	while totalClubs > 0:
		totalClubs -= 1
		ans = ans % mod * z % mod % mod
		z -= 1
	print(ans * pow(m, non, mod) % mod)