Creature Transformations

You are given a transformation matrix \(T\) of size \(N \times N\) where each element is either 0 or 1. Here, \(T[i][j] = 1\) indicates that creature type \(i\) can transform into creature type \(j\) in a single transformation. In addition, you are given several queries. Each query consists of two integers \(k\) and \(x\), where \(x\) is the initial creature type (1-indexed) and \(k\) is the exact number of transformations to perform.

Your task is to determine, for each query, the set of creature types that can be obtained by applying exactly \(k\) transformations starting from creature \(x\). Note that when \(k=0\), the creature remains unchanged, i.e. the transformation is the identity matrix \(I_N\). If there is no valid transformation (i.e. no creature is reachable), output -1 instead.

Input follows modulo 2 arithmetic, meaning all operations on the transformation matrix are computed mod 2. Use binary exponentiation to efficiently compute \(T^k\).

inputFormat

The first line contains two integers \(N\) and \(Q\) separated by a space, where \(N\) is the number of creature types and \(Q\) is the number of queries.

The next \(N\) lines each contain \(N\) space-separated integers (either 0 or 1) representing the transformation matrix \(T\).

Each of the following \(Q\) lines contains two integers \(k\) and \(x\):

• \(k\): the exact number of transformations.
• \(x\): the initial creature type (1-indexed).

outputFormat

For each query, print a line containing the following:

• If there exists at least one creature reachable after exactly \(k\) transformations, first print the number of reachable creature types, followed by the sorted list of these creature types (space-separated).
• If no creature is reachable, print 0 -1.

## sample

5 3
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0
2 1
1 3
0 5

1 3
1 4
1 5

</p>