Valid m-ary Heap Determination

You are given a sequence of n nodes labeled from 1 to n. Each node i has k parameters \(a_{i,1}, a_{i,2}, \dots, a_{i,k}\). The sequence is the BFS order of a max-heap constructed as a complete m-ary tree. In a BFS order, nodes are visited level by level, following the order shown by the red numbers in the figure below.

A max-heap satisfies the condition that for every node \(u\) and every child \(v\) of \(u\),
\[ \forall j\in[1,k],\quad a_{v,j}\le a_{u,j}, \]
that is, every parameter of every child is less than or equal to the corresponding parameter of its parent.

Assume that the heap is a complete m-ary tree. Your task is to find all integers \(m\) with \(1\le m\le n-1\) such that if the given sequence is interpreted as the BFS order of a complete m-ary tree, the max-heap property holds.

Note: In a complete m-ary tree (nodes indexed from 1), for any node with index \(i\), its children (if any) occupy the indices from \(m(i-1) + 2\) to \(m(i-1) + m + 1\) (provided these indices are \(\le n\)).

inputFormat

The first line of input contains two integers n and k representing the number of nodes and the number of parameters per node respectively.

Then follow n lines. The i-th line (1-indexed) contains k integers \(a_{i,1}, a_{i,2}, \dots, a_{i,k}\), which represent the parameters of the i-th node in the BFS order of the heap.

outputFormat

Print all valid values of m (in increasing order) separated by a space. If there is no such m, print -1.

sample

7 1
10
9
8
7
6
5
4

1 2 3 4 5 6