P9224 "PEOI Rd1" $k$-ary Heap

**Constraints are stronger than during the contest**. - 2023.04.25: The 1.50 s time limit was too tight due to constant factors, so it was increased to 2.00 s.

Given a sequence of positions $1 \sim n$, each position $i$ has $k$ parameters $a_{i,1}, a_{i,2}, \dots, a_{i,k}$. It is known that this sequence is obtained by taking the BFS order of a max-heap. The BFS order is the order of the **red numbered nodes** in the figure below:  A max-heap satisfies the condition if and only if, for every child node, **all** of its $k$ values are less than or equal to those of its parent, i.e., $\forall u \in [1,n], \forall v \in son(u), \forall j \in [1,k], a_{v,j} \leq a_{u,j}$. Assume this max-heap is a **complete $m$-ary tree**. Find all $m \in [1,n-1]$ such that this $m$-ary heap **satisfies the condition**.

The first line contains two integers $n, k$. Then follow $k$ lines, each containing $n$ integers, describing the given sequence. Specifically, the value in row $i+1$ and column $j$ is $a_{j,i}$. You can understand this as: all $k$ parameters for all positions are given, split into $k$ lines.

The first line contains an integer $A$, the number of possible values of $m$. The next line contains $A$ integers, the possible values of $m$.

#### Sample Explanation In Sample $1$, both $1$-ary and $2$-ary heaps obviously satisfy the condition. --- #### Constraints |Subtask ID|$n \leq$|Score| |:-:|:-:|:-:| |$1$|$10^3$|$20$| |$2$|$5 \times 10^4$|$20$| |$3$|$2 \times 10^5$|$60$| For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 2 \times 10^5$, $1 \leq k \leq 8$, and $-10^7 \leq a_{i,j} \leq 10^7$. Translated by ChatGPT 5