Hide

Problem J
Permutation Arrays

Lord Pooty loves permutations. However, what’s more interesting than permutations are arrays of permutations. He has $X$, a hidden array of $m$ permutations, each of length $n$. He also has $k$ constraints regarding $X$ that will be elaborated below.

A permutation of $n$ elements is an array of length $n$ containing each integer from $1$ to $n$ exactly once. For example, $[1,2,3]$ and $[4,3,5,1,2]$ are permutations but $[1,2,4]$ and $[4,3,2,1,2]$ are not.

Define an operator $*$ that takes an array $A$ containing elements from $1$ to $n$ (not necessarily distinct) and another array $B$ and returns a resultant array $C$ of length $n$ by the following way:

  • Each element $A_{i}$ in $A$ will be mapped to whatever element is in $B$ with $A_{i}$ as its position.

  • Formally, $A*B = C$ such that $C_{i} = B_{A_{i}}$.

For example, $[1,2,2,3,3,4] * [2,3,1,3] = [2,3,3,1,1,3]$

Constraints are given of the form $l$ $r$ $F$. This means the elements of $X$ satisfy the following: $((S*X_{l})*X_{l+1})*\ldots X_{r} = F$ where $S$ is an array of length $n$ satisfying $S_{i} = i$.

Lord Pooty has heard tales of your great genius and wanted to test if you are truly the genius the legends speak of. His original task for lesser feeble minds is to find how many different $X$ he can have that satisfy all $k$ constraints. However, that will be far too trivial for someone as great as yourself. As such, he will give you the constraints one by one. Every time you receive a constraint, you are to find how many different $X$ he can have that satisfy all the constraints that he has previously given. Since the numbers may be very large, you are to divide the answer by 998244353 and print the remainder. Prove your genius, or Lord Pooty may be disappointed and have your head chopped after the contest!

Two permutations $P$ and $Q$ are said to be different if there exists a $i$ such that $P_{i} \neq Q_{i}$.

Two arrays of permutations $X$ and $Y$ are considered different if there exist a $i$ such $X_{i}$ is different from $Y_{i}$.

The problem is interactive! You must answer a query before receiving the next one!

Input

The first line contains integers $m, n, k$ ($1 \leq m \leq 200\, 000$, $1 \leq n,k \leq 2\, 000$). This is followed by $k$ lines, each with $n+2$ integers: $l, r$, followed by $n$ integers $f_{1}, f_{2}, \ldots , f_{n}$ ($1 \leq l \leq r \leq m$, $1 \leq f_{i} \leq n$ for all $1 \leq i \leq n$).

Output

Output $k$ lines, each with an integer denoting the remainder of the answer divided by 998244353 after receiving each constraint.

Sample Input 1 Sample Output 1
3 2 2
1 1 2 1
1 2 1 2
4
2
CPU Time limit 2 seconds
Memory limit 1024 MB
Statistics Show
Author
Aloysius Lim Dewen
Source NUS Competitive Programming
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in