subset, solution in rational numbers

/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com5
 * Date: 2013.10.04
 *
 * Status: Accepted, Time = 1.4
 */

#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

typedef long long ll;

const ll P = (int)1e9 + 7;
const int N = 1000;
const int D = 10;

struct num
{
  ll a, b;

  num() { }
  num( ll a, ll b ) : a(a), b(b) { assert(b != 0); }

  void norm()
  {
    if (b == 1)
      return;
    ll g = __gcd(a, b);
    a /= g, b /= g;
    if (b < 0)
      a = -a, b = -b;
  }

  num operator + ( num x ) { return num(a * x.b + b * x.a, x.b * b); }
  num operator - ( num x ) { return num(a * x.b - b * x.a, x.b * b); }
  num operator * ( num x ) { return num(a * x.a, b * x.b); }
  num operator / ( num x ) { return num(a * x.b, b * x.a); }
  num operator ~ () { return num(b, a); }
  bool operator ! () { return a == 0; }

  bool operator == ( num x ) { return a * x.b - b * x.a == 0; }
  bool operator != ( num x ) { return a * x.b - b * x.a != 0; }
  bool operator < ( num x ) { return a * x.b - b * x.a < 0; }
  bool operator > ( num x ) { return a * x.b - b * x.a > 0; }

  #define DECLARE(s) \
    num& operator s##= ( num x ) { return *this = (*this s x); }
  DECLARE(+)
  DECLARE(-)
  DECLARE(*)
  DECLARE(/)
};

int n, d, a[N][D];
int pn, p[N];
int rn, rp[N];

int cn, id[3], ind[N], o[N];
ll c[N];
num b[D];

inline bool vless( int i, int j )
{
  return c[i] < c[j];
}

inline ll hash()
{
  int pos = 0;
  while (pos < d && !b[pos])
    pos++;
  num t = b[pos];
  forn(i, d)
    if (!!b[i])
      b[i] /= t;
  forn(i, d)
    b[i].norm();
  ll h = 0;
  forn(i, d)
  {
    h = h * P + b[i].a;
    h = h * P + b[i].b;
  }
  return h;
}

int main()
{
  #define NAME "subset"
  assert(freopen(NAME ".in", "r", stdin));
  assert(freopen(NAME ".out", "w", stdout));

  assert(scanf("%d%d", &n, &d) == 2 && n <= N && d <= D);
  forn(i, n)
    forn(j, d)
      assert(scanf("%d", &a[i][j]) == 1);
  forn(i, n)
  {
    pn = cn = 0;

    int pos = 0;
    while (!a[i][pos])
      pos++;
    forn(j, i)
    {
      int good = 1;
      forn(k, d)
        b[k] = num(a[j][k], 1);
      if (a[j][pos])
      {
        num koef(a[j][pos], a[i][pos]);
        good = 0;
        forn(k, d)
          if (!!(b[k] -= koef * num(a[i][k], 1)))
            good = 1;
      }
      if (!good)
        p[pn++] = j;
      else
      {
        c[cn] = hash();
        o[cn] = cn, ind[cn++] = j;
      }
    }
    sort(o, o + cn, vless);

    int ma = 0, rj = 0;
    for (int j = 0, k; j < cn; j = k)
    {
      for (k = j + 1; k < cn && !vless(o[j], o[k]); k++)
        ;
      if (k - j > ma)
        ma = k - j, rj = j;
    }
    if (ma + pn + 1 > rn)
    {
      rn = ma + pn + 1;
      forn(j, pn)
        rp[j] = p[j];
      forn(j, ma)
        rp[j + pn] = ind[o[rj + j]];
      rp[ma + pn] = i;
    }
  }
  printf("%d\n", rn);
  forn(i, rn)
    printf("%d%c", rp[i] + 1, " \n"[i == rn - 1]);
  return 0;
}