#include #include #define rep(i,n) for(int i=0;i vi; typedef vector vl; typedef vector> vvi; typedef vector> vvl; typedef long double ld; typedef pair P; ostream& operator<<(ostream& os, const modint& a) {os << a.val(); return os;} template ostream& operator<<(ostream& os, const static_modint& a) {os << a.val(); return os;} template ostream& operator<<(ostream& os, const dynamic_modint& a) {os << a.val(); return os;} template istream& operator>>(istream& is, vector& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;} template ostream& operator<<(ostream& os, const pair& p){os << p.first << ' ' << p.second; return os;} template ostream& operator<<(ostream& os, const vector& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;} template ostream& operator<<(ostream& os, const vector>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;} template ostream& operator<<(ostream& os, const set& se){for(T x : se) os << x << " "; os << "\n"; return os;} template ostream& operator<<(ostream& os, const unordered_set& se){for(T x : se) os << x << " "; os << "\n"; return os;} template ostream& operator<<(ostream& os, const atcoder::segtree& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;} template ostream& operator<<(ostream& os, const atcoder::lazy_segtree& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;} template void chmin(T& a, T b){a = min(a, b);} template void chmax(T& a, T b){a = max(a, b);} // https://youtu.be/ylWYSurx10A?t=2352 template struct Matrix : vector> { int h, w; Matrix(int h, int w, T val=0): vector>(h, vector(w, val)), h(h), w(w) {} Matrix(initializer_list> a) : vector>(a.begin(), a.end()){ assert(int(this->size()) >= 1); assert(int((*this)[0].size()) >= 1); h = this->size(); w = (*this)[0].size(); rep(i, h) assert(int((*this)[i].size()) == w); } Matrix& unit() { assert(h == w); rep(i,h) (*this)[i][i] = 1; return *this; } Matrix operator*=(const Matrix& M){ assert(w == M.h); Matrix r(h, M.w); rep(i,h) rep(k,w) rep(j, M.w){ r[i][j] += (*this)[i][k] * M[k][j]; } swap(*this, r); return *this; } Matrix operator*(const Matrix& M) const {return (Matrix(*this) *= M);} Matrix operator*=(const T& a) { for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) (*this)[i][j] *= a; return *this; } Matrix operator*(const T& a) const {return (Matrix(*this) *= a);} Matrix operator+=(const Matrix& M){ assert(h == M.h and w == M.w); for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) (*this)[i][j] += M[i][j]; return *this; } Matrix operator+(const Matrix& M) const {return (Matrix(*this) += M);} Matrix pow(long long t) const { assert(h == w); if (!t) return Matrix(h,h).unit(); if (t == 1) return *this; Matrix r = pow(t>>1);r = r*r; if (t&1) r = r*(*this); return r; } }; template pair> eliminate(Matrix a){ int h = a.h; int w = a.w; int ny = 0; rep(x, w){ for(int y = ny; y < h; y++){ if(a[y][x] != T(0)){ swap(a[y], a[ny]); break; } } if(a[ny][x] == T(0)) continue; rep(y, h){ if(y != ny and a[y][x] != T(0)){ T c = a[y][x] / a[ny][x]; rep(x, w){ a[y][x] -= a[ny][x] * c; } } } ny++; if(ny == h) break; } return make_pair(ny, a); }; // time: O(HW + rank(W - rank)) // space: O(HW + W(W - rank)) // solve aM = b // a = a_0 + Sum_{i=1,...,w - rank} c_i a_i // c_i is arbitrary constant template tuple, vector>> solve(Matrix mat, vector b){ int h = mat.h; int w = mat.w; assert(h == int(b.size())); { Matrix mat_new(h, w + 1); rep(y, h) rep(x, w) mat_new[y][x] = mat[y][x]; rep(y, h) mat_new[y][w] = b[y]; swap(mat, mat_new); } int rank; { auto res = eliminate(mat); rank = res.first; mat = res.second; } vector fixed; vector unfixed; { int y = 0; rep(x, w){ if(y == h){ unfixed.push_back(x); continue; } if(mat[y][x] == T(0)){ unfixed.push_back(x); }else{ fixed.push_back(x); y++; } } for(; y < h; y++){ if(mat[y][w] != T(0)){ return make_tuple(-1, vector(0), vector>(0)); } } } int freedom = w - rank; vector a_0(w); vector> a_vec(freedom); { rep(y, rank) a_0[fixed[y]] = mat[y][w] / mat[y][fixed[y]]; } rep(i, freedom){ a_vec[i].resize(w); a_vec[i][unfixed[i]] = 1; rep(y, rank) a_vec[i][fixed[y]] = -(mat[y][unfixed[i]]) / mat[y][fixed[y]]; break; } return make_tuple(freedom, a_0, a_vec); } using mint = modint; const int M = 60; int main(){ mint::set_mod(2); int n; cin >> n; vector a(n); cin >> a; Matrix mat(M, n); rep(i, n){ rep(j, M){ if((a[i] >> j) & 1) mat[j][i] = 1; } } vector zero(M); auto [freedom, a_0, a_vec] = solve(mat, zero); if(freedom == -1 or freedom == 0){ cout << "-1\n"; return 0; }else{ { vector ans; rep(i, n) if(a_vec[0][i] != mint(0)) ans.push_back(i); cout << ans.size() <<" \n"; for(int idx : ans) cout << idx + 1 << ' '; } } return 0; }