You are given a set of n≥ 2 pairwise different points with integer coordinates. Your task is to partition these points into two nonempty groups A and B, such that the following condition holds:

For every two points P and Q, write the [Euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance) between them on the blackboard: if they belong to the same group — with a yellow pen, and if they belong to different groups — with a blue pen. Then no yellow number is equal to any blue number.

It is guaranteed that such a partition exists for any possible input. If there exist multiple partitions, you are allowed to output any of them.

Input

The first line contains one integer n (2 ≤ n ≤ 10^3) — the number of points.

The i-th of the next n lines contains two integers x_i and y_i (-10^6 ≤ x_i, y_i ≤ 10^6) — the coordinates of the i-th point. 

It is guaranteed that all n points are pairwise different.

Output

In the first line, output a (1 ≤ a ≤ n-1) — the number of points in a group A.

In the second line, output a integers — the indexes of points that you include into group A.

If there are multiple answers, print any.

Examples

Input


3
0 0
0 1
1 0


Output


1
1 

Input


4
0 1
0 -1
1 0
-1 0


Output


2
1 2 

Input


3
-2 1
1 1
-1 0


Output


1
2 

Input


6
2 5
0 3
-4 -1
-5 -4
1 0
3 -1


Output


1
6 

Input


2
-1000000 -1000000
1000000 1000000


Output


1
1 

Note

In the first example, we set point (0, 0) to group A and points (0, 1) and (1, 0) to group B. In this way, we will have 1 yellow number √{2} and 2 blue numbers 1 on the blackboard.

In the second example, we set points (0, 1) and (0, -1) to group A and points (-1, 0) and (1, 0) to group B. In this way, we will have 2 yellow numbers 2, 4 blue numbers √{2} on the blackboard.

Difficulty: HARD
Tags: Geometry

Mathematics

Constructive algorithms

Starter code:

Solutions:
import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List
N = int(input())
A = []
for i in range(N):
	(x, y) = map(int, input().split())
	A.append((x, y))

def dist(a, b):
	return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
while True:
	a = {i for i in range(N) if A[i][0] % 2 == 0 and A[i][1] % 2 == 0}
	b = {i for i in range(N) if A[i][0] % 2 == 0 and A[i][1] % 2 == 1}
	c = {i for i in range(N) if A[i][0] % 2 == 1 and A[i][1] % 2 == 0}
	d = {i for i in range(N) if A[i][0] % 2 == 1 and A[i][1] % 2 == 1}
	if len([v for v in [a, b, c, d] if v]) == 1:
		A = [(x // 2, y // 2) for (x, y) in A]
		continue
	if not a and (not d):
		ans = b
	elif not b and (not c):
		ans = a
	else:
		ans = a | d
	ans = [i + 1 for i in ans]
	print(len(ans))
	print(' '.join(map(str, ans)))
	exit(0)


from math import gcd
n = int(input())
p = [list(map(int, input().split())) for i in range(n)]
G = 0
for i in range(n - 1, -1, -1):
	p[i][0] -= p[0][0]
	p[i][1] -= p[0][1]
	G = gcd(G, p[i][0])
	G = gcd(G, p[i][1])
m = 0
while G % 2 == 0:
	m += 1
	G //= 2
check1 = [0, 0]
for i in range(n):
	p[i][0] //= 2 ** m
	p[i][1] //= 2 ** m
	t = (p[i][0] - p[i][1]) % 2
	check1[t] += 1
if check1[0] * check1[1] != 0:
	a = []
	for i in range(n):
		t = (p[i][0] - p[i][1]) % 2
		if not t:
			a.append(i + 1)
	print(len(a))
	print(*a, sep='\n')
else:
	a = []
	for i in range(n):
		if p[i][0] % 2 == 0:
			a.append(i + 1)
	print(len(a))
	print(*a, sep='\n')


import sys

def solution():
	n = int(input().strip())
	a = [tuple((int(j) + 100000000 for j in input().strip().split())) for i in range(n)]
	if n == 2:
		sys.stdout.write('%d\n%d\n' % (1, 1))
		return
	while True:
		cnt = [[0, 0], [0, 0]]
		for p in a:
			cnt[p[0] & 1][p[1] & 1] += 1
		if max(map(max, cnt)) == n:
			dx = a[0][0] & 1
			dy = a[0][1] & 1
			for i in range(n):
				a[i] = (a[i][0] - dx >> 1, a[i][1] - dy >> 1)
			continue
		if cnt[0][0] + cnt[1][1] > 0 and cnt[0][0] + cnt[1][1] < n:
			sys.stdout.write('%d\n' % (cnt[0][0] + cnt[1][1]))
			first = True
			for i in range(n):
				if a[i][0] & 1 == a[i][1] & 1:
					if not first:
						sys.stdout.write(' ')
					else:
						first = False
					sys.stdout.write('%d' % (i + 1))
			sys.stdout.write('\n')
			return
		else:
			sys.stdout.write('%d\n' % (cnt[0][0] + cnt[0][1]))
			first = True
			for i in range(n):
				if a[i][0] & 1 == 0:
					if not first:
						sys.stdout.write(' ')
					else:
						first = False
					sys.stdout.write('%d' % (i + 1))
			sys.stdout.write('\n')
			return

def main():
	solution()
main()


def solve(XY):
	while True:
		groups = {}
		for i in range(len(XY)):
			(x, y) = XY[i]
			groups.setdefault((x % 2, y % 2), []).append(i)
		if len(groups) == 2:
			return next(iter(groups.values()))
		elif len(groups) > 2:
			return groups.get((0, 0), []) + groups.get((1, 1), [])
		XY = [(x // 2, y // 2) for (x, y) in XY]
n = int(input())
XY = [tuple((int(v) for v in input().split())) for _ in range(n)]
A = solve(XY)
print(len(A))
print(*(i + 1 for i in A))


n = int(input())
coord = [list(map(int, input().split())) for i in range(n)]
import sys
while True:
	mat = [[[], []], [[], []]]
	for i in range(n):
		mat[coord[i][0] % 2][coord[i][1] % 2].append(i + 1)
	niezer = 0
	if (mat[0][1] or mat[1][0]) and (mat[0][0] or mat[1][1]):
		a = mat[0][1] + mat[1][0]
		print(len(a))
		print(*a)
		sys.exit(0)
	else:
		if mat[0][0] or mat[1][1]:
			if mat[0][0] and (not mat[1][1]):
				for i in range(n):
					coord[i][0] //= 2
					coord[i][1] //= 2
			if mat[1][1] and (not mat[0][0]):
				for i in range(n):
					coord[i][0] -= 1
					coord[i][0] //= 2
					coord[i][1] -= 1
					coord[i][1] //= 2
			if mat[1][1] and mat[0][0]:
				print(len(mat[1][1]))
				print(*mat[1][1])
				sys.exit(0)
		if mat[0][1] or mat[1][0]:
			if mat[0][1] and (not mat[1][0]):
				for i in range(n):
					coord[i][1] -= 1
					coord[i][1] //= 2
					coord[i][0] //= 2
			if mat[1][0] and (not mat[0][1]):
				for i in range(n):
					coord[i][0] -= 1
					coord[i][0] //= 2
					coord[i][1] //= 2
			if mat[1][0] and mat[0][1]:
				print(len(mat[1][0]))
				print(*mat[1][0])
				sys.exit()


x = int(input())
pointlist = []
for i in range(x):
	(a, b) = map(int, input().strip().split())
	pointlist.append((a, b))
while True:
	outlist = []
	out = 0
	for i in range(x):
		(m, n) = (pointlist[i][0], pointlist[i][1])
		r = m + n
		if r % 2 == 0:
			outlist.append(str(i + 1))
			out += 1
	if out == 0:
		for j in range(x):
			s = (pointlist[j][0] + pointlist[j][1] + 1) // 2
			t = (pointlist[j][0] - pointlist[j][1] - 1) // 2
			pointlist[j] = (s, t)
	elif out == x:
		for j in range(x):
			s = (pointlist[j][0] + pointlist[j][1]) // 2
			t = (pointlist[j][0] - pointlist[j][1]) // 2
			pointlist[j] = (s, t)
	else:
		print(str(out))
		print(' '.join(outlist))
		break


import sys
input = sys.stdin.readline

def pow2fraction(n):
	return n & ~(n - 1)
n = int(input())
(xz, yz) = map(int, input().split())
ps = [[0, 0]]
minPow2 = float('inf')
for _ in range(n - 1):
	(x, y) = map(int, input().split())
	x -= xz
	y -= yz
	if x != 0:
		minPow2 = min(minPow2, pow2fraction(x))
	if y != 0:
		minPow2 = min(minPow2, pow2fraction(y))
	ps.append([x, y])
shift = len(bin(minPow2)) - 3
if shift > 0:
	for p in ps:
		p[0] >>= shift
		p[1] >>= shift
A00 = []
A10 = []
A01 = []
A11 = []
for (i, (x, y)) in enumerate(ps):
	if x % 2 and y % 2:
		A11.append(i + 1)
	elif x % 2 and (not y % 2):
		A10.append(i + 1)
	elif not x % 2 and y % 2:
		A01.append(i + 1)
	else:
		A00.append(i + 1)
if A10 or A01:
	ans = A00 + A11
else:
	ans = A00
print(len(ans))
print(*ans)


import sys

def cin():
	return [int(i) for i in sys.stdin.readline().split()]
(n,) = cin()
(x0, y0) = cin()
arr = [0]
for i in range(n - 1):
	(x, y) = cin()
	arr.append((x - x0) ** 2 + (y - y0) ** 2)
while not any((i & 1 for i in arr)):
	for j in range(n):
		arr[j] >>= 1
ans = [i + 1 for i in range(n) if arr[i] & 1]
sys.stdout.write('{0}\n'.format(str(len(ans))))
sys.stdout.write(' '.join((str(i) for i in ans)))


from collections import Counter
from sys import stdout

def solve(ee, eo, oe, oo):
	if len(ee) + len(oo) > 0 and len(eo) + len(oe) > 0:
		print(len(ee) + len(oo))
		ans = [x[-1] + 1 for x in ee + oo]
		print(*ans)
		return
	if len(ee) > 0 and len(oo) > 0 and (len(eo) + len(oe) == 0):
		print(len(ee))
		print(*[x[-1] + 1 for x in ee])
		return
	if len(ee) + len(oo) == 0 and len(eo) > 0 and (len(oe) > 0):
		print(len(eo))
		print(*[x[-1] + 1 for x in eo])
		return
	if len(ee) > 0 and len(eo) + len(oe) + len(oo) == 0:
		for i in range(len(ee)):
			ee[i][0] //= 2
			ee[i][1] //= 2
		return solve(*split(ee))
	if len(eo) > 0 and len(ee) + len(oe) + len(oo) == 0:
		for i in range(len(eo)):
			eo[i][1] += 1
		return solve(eo, [], [], [])
	if len(oe) > 0 and len(ee) + len(eo) + len(oo) == 0:
		for i in range(len(oe)):
			oe[i][0] += 1
		return solve(oe, [], [], [])
	if len(oo) > 0 and len(ee) + len(eo) + len(oe) == 0:
		for i in range(len(oo)):
			oo[i][0] += 1
			oo[i][1] += 1
		return solve(oo, [], [], [])

def split(dots):
	(ee, eo, oe, oo) = [[] for _ in range(4)]
	for (x, y, i) in dots:
		if x % 2 == 0 and y % 2 == 0:
			ee.append([x, y, i])
		elif x % 2 == 1 and y % 2 == 0:
			oe.append([x, y, i])
		elif x % 2 == 0 and y % 2 == 1:
			eo.append([x, y, i])
		else:
			oo.append([x, y, i])
	return (ee, eo, oe, oo)

def solvee():
	n = int(input())
	dots = []
	for i in range(n):
		(x, y) = (int(x) for x in input().split())
		dots.append([x, y, i])
	solve(*split(dots))
t = 1
for _ in range(t):
	solvee()


n = int(input())
p = []

def contar_paridades(p):
	(oo, oe, eo, ee) = (0, 0, 0, 0)
	for (x, y) in p:
		if x & 1 and y & 1:
			oo += 1
		elif x & 1:
			oe += 1
		elif y & 1:
			eo += 1
		else:
			ee += 1
	return (ee, eo, oe, oo)

def todas_en_una(p):
	(ee, eo, oe, oo) = contar_paridades(p)
	not_null = bool(ee) + bool(eo) + bool(oe) + bool(oo)
	return not_null == 1
for i in range(n):
	(x, y) = map(int, input().split())
	p.append([x, y])
while todas_en_una(p):
	for i in range(n):
		p[i][0] //= 2
		p[i][1] //= 2
(ee, eo, oe, oo) = contar_paridades(p)
if ee and oo and (not eo) and (not oe):
	print(ee)
	ans = [i + 1 for i in range(n) if not p[i][0] & 1]
	print(*ans)
elif not ee and (not oo) and eo and oe:
	print(eo)
	ans = [i + 1 for i in range(n) if not p[i][0] & 1]
	print(*ans)
else:
	print(ee + oo)
	ans = [i + 1 for i in range(n) if not p[i][0] + p[i][1] & 1]
	print(*ans)


def divide(n, points):
	loop = 2
	while True:
		dic = {}
		for i in range(n):
			(x, y) = points[i]
			if (x + y) % loop not in dic:
				dic[(x + y) % loop] = []
			dic[(x + y) % loop].append(i + 1)
		if len(dic) == 2:
			for ele in dic:
				print(len(dic[ele]))
				print(' '.join([str(i) for i in dic[ele]]))
				return
		dic = {}
		for i in range(n):
			x = points[i][0]
			if x % loop not in dic:
				dic[x % loop] = []
			dic[x % loop].append(i + 1)
		if len(dic) == 2:
			for ele in dic:
				print(len(dic[ele]))
				print(' '.join([str(i) for i in dic[ele]]))
				return
		loop *= 2
n = int(input())
points = []
for i in range(n):
	(x, y) = map(int, input().split())
	points.append([x, y])
divide(n, points)


from sys import stdin

def rl():
	return [int(w) for w in stdin.readline().split()]
(n,) = rl()
(x0, y0) = rl()
d = [0]
for i in range(n - 1):
	(x, y) = rl()
	d.append((x - x0) ** 2 + (y - y0) ** 2)
while not any((x & 1 for x in d)):
	for i in range(n):
		d[i] >>= 1
A = [i + 1 for i in range(n) if d[i] & 1]
print(len(A))
print(*A)


import sys
input = sys.stdin.readline
n = int(input())
P = [tuple(map(int, input().split())) for i in range(n)]
while True:
	ANS = []
	for i in range(n):
		(x, y) = P[i]
		if (x + y) % 2 == 0:
			ANS.append(i + 1)
	if len(ANS) != 0 and len(ANS) != n:
		print(len(ANS))
		print(*ANS)
		sys.exit()
	if (x + y) % 2 == 0:
		for i in range(n):
			(x, y) = P[i]
			P[i] = ((x + y) // 2, (x - y) // 2)
	else:
		for i in range(n):
			(x, y) = P[i]
			P[i] = ((x + 1 + y) // 2, (x + 1 - y) // 2)


from collections import Counter

def main():
	n = int(input())
	pp = []
	gg = [[[], []], [[], []]]
	for i in range(n):
		(x, y) = map(int, input().split())
		pp.append((x, y))
		gg[x % 2][y % 2].append(i)
	while len([len(gg[i][j]) for i in range(2) for j in range(2) if len(gg[i][j]) > 0]) <= 1:
		gg = [[[], []], [[], []]]
		for (i, (x, y)) in enumerate(pp):
			pp[i] = (x // 2, y // 2)
			gg[x % 2][y % 2].append(i)
	if not gg[0][0] and (not gg[1][1]):
		aa = gg[1][0]
	elif not gg[1][0] and (not gg[0][1]):
		aa = gg[0][0]
	else:
		aa = gg[0][0] + gg[1][1]
	aa = [a + 1 for a in aa]
	print(len(aa))
	print(' '.join(map(str, aa)))
main()


n = int(input())
points = [tuple(map(int, input().split())) for i in range(n)]
power = 1
while True:
	A = [1]
	(x0, y0) = points[0]
	for (i, (x1, y1)) in enumerate(points[1:], start=2):
		if (abs(y1 - y0) + abs(x1 - x0)) // power % 2 == 0:
			A.append(i)
	if len(A) < n:
		break
	A = [1]
	(x0, y0) = points[0]
	for (i, (x1, y1)) in enumerate(points[1:], start=2):
		if abs(y1 - y0) // power % 2 == 0 and abs(x1 - x0) // power % 2 == 0:
			A.append(i)
	if len(A) < n:
		break
	power *= 2
print(len(A))
print(*A)


def gen_keys():
	mod = 2
	while True:
		yield (lambda i1: sum(inp[i1]) % mod)
		yield (lambda i1: inp[i1][1] % mod)
		mod *= 2
n = int(input())
inp = [tuple(map(int, input().split())) for _ in range(n)]
for key in gen_keys():
	k1 = key(1)
	ans = [i for i in range(n) if key(i) == k1]
	if len(ans) not in (0, n):
		print(len(ans))
		print(*(ansi + 1 for ansi in ans))
		break


import sys
n = int(sys.stdin.readline().strip())
x = [0] * n
y = [0] * n
z = [0] * n
for i in range(0, n):
	(x[i], y[i]) = list(map(int, sys.stdin.readline().strip().split()))
	z[i] = (x[i] + y[i]) % 2
while sum(z) % n == 0:
	if z[0] == 1:
		for i in range(0, n):
			x[i] = x[i] + 1
	for i in range(0, n):
		(x[i], y[i]) = ((x[i] + y[i]) // 2, (x[i] - y[i]) // 2)
		z[i] = (x[i] + y[i]) % 2
print(sum(z))
ans = []
for i in range(0, n):
	if z[i] == 1:
		ans.append(str(i + 1))
print(' '.join(ans))


import sys, math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return s[:len(s) - 1]

def invr():
	return map(int, input().split())
t = 1
for tt in range(t):
	n = inp()
	a = []
	for i in range(n):
		a.append(inlt())
	while True:
		qw = [(j + q) % 2 for (j, q) in a]
		if 0 != sum(qw) != len(a):
			print(int(sum(qw)))
			for (i, j) in enumerate(qw):
				if j:
					print(i + 1, end=' ')
			print()
			sys.exit()
		a = [((a[i][0] + a[i][1] + qw[i]) / 2, (a[i][0] - a[i][1] + qw[i]) / 2) for i in range(len(a))]


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	n = mint()
	p = [None] * n
	for i in range(n):
		p[i] = tuple(mints())
	(bx, by) = p[0]
	(orx, ory) = (0, 0)
	for i in p:
		orx |= i[0] ^ bx
		ory |= i[1] ^ by
	orx -= orx & orx - 1
	ory -= ory & ory - 1
	if orx == 0:
		orx = int(1000000000.0)
	if ory == 0:
		ory = int(1000000000.0)
	d = min(orx, ory)
	c = [[[], []], [[], []]]
	for i in range(len(p)):
		(x, y) = p[i]
		c[x // d % 2][y // d % 2].append(i + 1)
	A = []
	if len(c[0][0]) + len(c[1][1]) != 0:
		if len(c[1][0]) + len(c[0][1]) != 0:
			A = c[0][0] + c[1][1]
		else:
			A = c[0][0]
	else:
		A = c[0][1]
	print(len(A))
	print(' '.join(map(str, A)))
solve()


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
while True:
	even = []
	odd = []
	for i in range(n):
		(x, y) = info[i]
		if (x + y) % 2 == 0:
			even.append(i + 1)
		else:
			odd.append(i + 1)
	if len(even) * len(odd) != 0:
		print(len(even))
		print(*even)
		exit()
	tmp = 0
	if len(odd) == n:
		tmp = 1
	for i in range(n):
		(x, y) = info[i]
		x += tmp
		info[i][0] = (x + y) // 2
		info[i][1] = (x - y) // 2


n = int(input())
a = []
for i in range(n):
	(x, y) = map(int, input().split())
	a.append((x, y, i))
chk = lambda a: (a[0] + a[1]) % 2
rot = lambda a: (lambda x, y, i: ((x + y) // 2, (y - x) // 2, i))(*a)
while 1:
	u = []
	v = []
	for z in a:
		if chk(z):
			u.append(z)
		else:
			v.append(z)
	if len(u) > 0 and len(v) > 0:
		print(len(u))
		print(*[i + 1 for (_, _, i) in u])
		exit()
	else:
		a = list(map(rot, a))


n = int(input())
a = [list(map(int, input().split())) + [i] for i in range(n)]

def classify(a):
	(ee, eo, oe, oo) = ([], [], [], [])
	for (x, y, i) in a:
		if x & 1 == 0 and y & 1 == 0:
			ee.append([x, y, i])
		elif x & 1 == 0 and y & 1 == 1:
			eo.append([x, y, i])
		elif x & 1 == 1 and y & 1 == 0:
			oe.append([x, y, i])
		else:
			oo.append([x, y, i])
	return (ee, eo, oe, oo)

def ok():
	return (len(ee) > 0) + (len(eo) > 0) + (len(oe) > 0) + (len(oo) > 0) > 1
(ee, eo, oe, oo) = classify(a)
while not ok():
	a = ee or eo or oe or oo
	for i in range(n):
		a[i][0] //= 2
		a[i][1] //= 2
	(ee, eo, oe, oo) = classify(a)
if (ee or oo) and (eo or oe):
	group = ee + oo
elif ee and oo:
	group = ee
elif eo and oe:
	group = eo
else:
	raise Exception
ret = [i + 1 for (x, y, i) in group]
print('%d\n%s' % (len(ret), ' '.join(map(str, ret))))


n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]
while True:
	a_count = b_count = 0
	for (x, y) in points:
		if x + y & 1:
			a_count += 1
		else:
			b_count += 1
	if a_count and b_count:
		a = []
		for (i, point) in enumerate(points):
			if sum(point) & 1:
				a.append(i + 1)
		print(a_count)
		print(' '.join(map(str, a)))
		break
	points = [((x + y) // 2, (x - y) // 2) for (x, y) in points]


import sys
n = int(input())
xy = []
for i in range(n):
	(x, y) = map(int, input().split())
	xy.append([x, y])
loop = 2
while True:
	dic = {}
	for i in range(n):
		x = xy[i][0]
		y = xy[i][1]
		if (x + y) % loop not in dic:
			dic[(x + y) % loop] = []
		dic[(x + y) % loop].append(i + 1)
	if len(dic) == 2:
		for i in dic:
			print(len(dic[i]))
			print(' '.join(map(str, dic[i])))
			sys.exit()
	dic = {}
	for i in range(n):
		x = xy[i][0]
		if x % loop not in dic:
			dic[x % loop] = []
		dic[x % loop].append(i + 1)
	if len(dic) == 2:
		for i in dic:
			print(len(dic[i]))
			print(' '.join(map(str, dic[i])))
			sys.exit()
	loop *= 2


n = int(input())
ps = []
for i in range(n):
	ps.append(list(map(int, input().split())))
if n == 2:
	print(1)
	print(1)
else:
	ee = []
	eo = []
	oe = []
	oo = []
	while True:
		for (i, p) in zip(range(n), ps):
			if p[0] % 2 == 0 and p[1] % 2 == 0:
				ee.append(i + 1)
			elif p[0] % 2 == 1 and p[1] % 2 == 0:
				oe.append(i + 1)
			elif p[0] % 2 == 0 and p[1] % 2 == 1:
				eo.append(i + 1)
			else:
				oo.append(i + 1)
			if p[0] % 2 == 1:
				p[0] -= 1
			if p[1] % 2 == 1:
				p[1] -= 1
			p[0] = p[0] / 2
			p[1] = p[1] / 2
		a = None
		b = None
		for i in (ee, eo, oe, oo):
			for j in (ee, eo, oe, oo):
				if i == j:
					continue
				if i and j and (len(i) + len(j) == n):
					a = i
					b = j
		if a != None:
			print(len(a))
			print(' '.join(map(str, a)))
			break
		if (eo or oe) and (oo or ee):
			eo.extend(oe)
			a = eo
		if a != None:
			print(len(a))
			print(' '.join(map(str, a)))
			break
		ee.clear()
		eo.clear()
		oe.clear()
		oo.clear()


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline

def factors(n):
	return sorted(list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n').split(' ')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
n = val()
l = []
index = {}
for i in range(n):
	l.append(li())
	index[tuple(l[i])] = i
even = odd = 0
A = set()
B = set()
C = set()
D = set()
for i in l:
	even = max(even, 0 if sum(i) & 1 else 1)
	odd = max(odd, 1 if sum(i) & 1 else 0)
	if i[0] & 1:
		if i[1] & 1:
			D.add(tuple(i))
		else:
			C.add(tuple(i))
	elif i[1] & 1:
		B.add(tuple(i))
	else:
		A.add(tuple(i))
while sum((1 for i in [A, B, C, D] if len(i))) == 1:
	index = {}
	even = odd = 0
	for i in range(len(l)):
		l[i] = [l[i][0] // 2, l[i][1] // 2]
		index[tuple(l[i])] = i
	A = set()
	B = set()
	C = set()
	D = set()
	for i in l:
		even = max(even, 0 if sum(i) & 1 else 1)
		odd = max(odd, 1 if sum(i) & 1 else 0)
		if i[0] & 1:
			if i[1] & 1:
				D.add(tuple(i))
			else:
				C.add(tuple(i))
		elif i[1] & 1:
			B.add(tuple(i))
		else:
			A.add(tuple(i))
if even == odd == 1:
	A = set()
	for i in l:
		if sum(i) & 1:
			A.add(tuple(i))
else:
	for i in [A, B, C, D]:
		if len(i):
			A = i
print(len(A))
for i in A:
	print(index[i] + 1)