Кот Бенедикт любит наблюдать из окна за происходящим в парке. На одном из газонов парка устроили инсталляцию из камней. Мелкие камни образуют равномерную сетку из квадратов со стороной длины $$$1$$$, а в трех узлах сетки расположены валуны. Эти валуны давно облюбовали три уличных кота — на них можно греться в прохладный, но солнечный осенний день.
Иногда коты меняются местами: первый отправляется на место второго, второй на место третьего, а третий — на место первого. Коты перемещаются исключительно по мелким камням: газон влажный, и они не хотят пачкать лапки. Именно это коты и задумали сделать, но... В один из узлов сетки пришёл четвёртый кот, имеющий намерение занять один из тёплых валунов.
Коты планировали одновременно покинуть те валуны, на которых они располагаются, и отправиться по кратчайшему пути (по дорожкам из камней) к тем валунам, на которых они хотят расположиться. Их интересует, смогут ли они сделать это, или же кого-то из них сможет опередить четвёртый кот.
Считайте, что все четыре кота начинают двигаться одновременно, двигаются с одинаковой скоростью и только по дорожкам из мелких камней. Также считайте, что при движении они не помешают друг другу, даже если будут двигаться по одной дорожке. Вы можете быть уверены, что если один из трёх котов и четвёртый одновременно достигнут валуна, четвёртый кот окажется менее проворным и не сможет занять валун.
Выведите в качестве ответа количество валунов, к которым четвёртый кот может добраться строго быстрее других котов. Также выведите номера этих валунов.
В первой строке содержится номер горизонтальной дорожки, на которой располагается первый валун.
Во второй строке содержится номер вертикальной дорожки, на которой располагается первый валун.
В третьей строке содержится номер горизонтальной дорожки, на которой располагается второй валун.
В четвёртой строке содержится номер вертикальной дорожки, на которой располагается второй валун.
В пятой строке содержится номер горизонтальной дорожки, на которой располагается третий валун.
В шестой строке содержится номер вертикальной дорожки, на которой располагается третий валун.
В седьмой строке содержится номер горизонтальной дорожки, на которой располагается четвёртый кот.
В восьмой строке содержится номер вертикальной дорожки, на которой располагается четвёртый кот.
Все номера дорожек — положительные целые числа, не превосходящие $$$10000$$$.
Гарантируется, что все валуны расположены в разных узлах сетки. Также гарантируется, что четвёртый кот находится в узле сетки, отличном от положения какого-либо валуна.
В первой строке выведите количество валунов, к которым четвёртый кот может добраться строго быстрее других котов.
Далее выведите номера этих валунов в порядке возрастания. Разделяйте номера пробелами или переводами строки.
В этой задаче баллы начисляются независимо за каждый тест. Каждый из $$$20$$$ тестов оценивается в $$$5$$$ баллов. Тесты из условия не оцениваются.
58276433
1 3
58276447
3 1 2 3
58276456
2 1 3
Поясним приведённые примеры.
В первом примере четвёртый кот может опередить только второго кота и занять третий валун раньше него.
Первый кот отправится ко второму валуну и сможет достичь его, пройдя расстояние $$$4$$$ единицы. Четвёртому же коту до второго валуна нужно пройти $$$5$$$ единиц.
Второй кот отправится к третьему валуну, и его путь будет иметь длину $$$7$$$ единиц. А вот путь четвёртого кота до третьего валуна будет иметь длину $$$4$$$ единицы.
Наконец, третий кот отправится к первому валуну, и для этого ему потребуется преодолеть расстояние в $$$5$$$ единиц. Четвёртому же коту понадобится пройти $$$7$$$ единиц.
Во втором примере валуны находятся на тех же позициях, что и в первом примере, поэтому пути котов к валунам будут иметь ту же длину.
А вот четвёртый кот занял другое место.
Длина пути четвёртого кота до первого валуна составит $$$2$$$ единицы, поэтому он сможет опередить третьего кота, которому требуется пройти $$$5$$$ единиц длины.
Длина пути четвёртого кота до второго валуна также составит $$$2$$$ единицы, поэтому он сможет опередить и первого кота, которому требуется пройти $$$4$$$ единицы длины.
Наконец, длина пути четвёртого кота до третьего валуна составит $$$5$$$ единиц, поэтому он сможет опередить и второго кота, которому требуется пройти $$$7$$$ единиц длины.
Таким образом, четвёртый кот может достичь любого из валунов раньше того кота, который к нему направится.
В третьем примере валуны по-прежнему находятся на тех же позициях, что и в первом, и во втором примерах.
Четвёртый кот может опередить третьего на пути к первому валуну: длина пути четвёртого кота составит $$$2$$$ единицы, а длина пути третьего кота — $$$5$$$ единиц.
Также четвёртый кот может опередить второго кота на пути к третьему валуну: длина пути четвёртого кота составит $$$3$$$ единицы, а второму нужно проделать путь длиной $$$7$$$ единиц.
А вот ко второму валуну четвёртый кот придёт одновременно с первым: и тот, и другой преодолеют путь длиной $$$4$$$ единицы. Однако по условию задачи валун займет первый кот.
