Background

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.

Problem Description

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.

Input Format

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.

Output Format

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$.

3 2
1 1 1
1 1 1

2
1 2

6 1
2 1 2 1 1 2

2
2 5

Hint

Sample Explanation

In Sample $1$, both $1$-ary and $2$-ary heaps obviously satisfy the condition.

Constraints

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