This page is still under construction.

Parts of this page are still being built. What you see may change.

Space Boomerang

Time limit3sMemory limit128 MB

Summary
Given M direction vectors in N-dimensional space, find every vector that cannot appear with a nonzero coefficient in any linear combination summing to zero.
Level

Hard8 of 10

Topics
Math, Geometry, Implementation
Solved
No attempts yet

Problem

Far outside of our universe, the children of hyperspace creatures play the following game. They have a "boomerang" toy that they can program and then throw. Naturally, they want it to come back to the same place.

To program the toy, they have a set of modules that they can install into it. Each module pushes the toy along one fixed direction. For every module they install, they enter a non-zero distance that the toy will travel along that module's direction (they do not have to install every module in a single game). A distance may be positive or negative; a negative distance means the toy travels in the opposite direction.

After programming, they throw the boomerang. It moves through space using all installed modules simultaneously, until they all run out of power. The toy returns to its starting point exactly when the vector sum of (distance ×\times direction) over the installed modules is zero. The children play many rounds, and modules may be reused between rounds.

They want to have as much fun as possible by using many different modules. However, some modules may be useless: it is impossible to install such a module (with a non-zero distance) together with any choice of the other modules and still make the boomerang return to its starting point. Help the children find every such useless module.

Input

The first line contains two integers MM and NN separated by a space (1≤M≤30001 \le M \le 3000, 1≤N≤3001 \le N \le 300), where MM is the number of modules and NN is the number of dimensions of the hyperspace.

Each of the next MM lines contains NN real numbers separated by spaces, giving the coordinates of one module's direction in NN-dimensional space. The modules are numbered 11 through MM in the order they appear in the input. Each coordinate has at most two digits after the decimal point, and its absolute value is at most 10510^5.

Output

On the first line, print one integer KK: the number of useless modules.

On each of the next KK lines, print the index of one useless module, in the same order as they appear in the input (that is, in increasing index order). If there are no useless modules, print only a line containing 00.

Examples3

  1. Example 1

    Input
    4 3
    0 0 1
    1 0 2
    0 1 0
    1 0 1
    
    Expected output
    1
    3
    
  2. Example 2

    Input
    1 2
    1 0
    
    Expected output
    1
    1
    
  3. Example 3

    Input
    1 3
    0 0 0
    
    Expected output
    0