eolymp
bolt
Try our new interface for solving problems
Problems

Платные дороги

Платные дороги

Time limit 2 seconds
Memory limit 256 MiB

Мэр одного большого города решил ввести оплату за проезд по шоссе, проходящим в районе города, чтобы снизить объём транзитного транспорта. В районе города проходит n шоссе.

Но руководство области, в которой расположен город, воспротивилось планам мэра. Действительно - дальнобойщики представляют собой неплохой источник доходов для большого количества кафе и гостиниц в небольших городах.

В результате решили, что плата будет произведена только на шоссе, которые проходят через город.

В городе используется развитая система метрополитена, всего в городе есть m станций метро. Было решено, что шоссе проходит через город, если либо одна из станций метро расположена непосредственно на шоссе, либо есть хотя бы одна станция с каждой стороны от шоссе.

Помогите теперь мэру определить, какие шоссе проходят через город.

Input data

Первая строка входного файла содержит два целых числа: n и m - количество шоссе и количество станций метро, соответственно (1n, m100000).

Следующие n строк описывают шоссе. Каждое шоссе описывается тремя целыми числами a, b и c и представляет собой прямую на плоскости, задаваемую уравнением ax+by+c=0 (|a|, |b|, |c| ≤ 10^6).

Следующие m строк входного файла описывают станции метро. Каждая станция описывается двумя целыми числами x и y и представляет собой точку на плоскости с координатами (x, y) (|x|, |y| ≤ 10^6).

Output data

Первая строка выходного файла должна содержать одно целое число - количество шоссе, которые проходят через город. Вторая строка должна содержать номера этих шоссе в возрастающем порядке. Шоссе нумеруются от 1 до n в порядке, в котором они описаны во входном файле.

Examples

Input example #1
4 2
0 1 0
1 0 1
1 1 0
1 1 -1
0 0
2 0
Output example #1
3
1 3 4