Задача A. Эльфы и олени ≡

Условие

Скоро новый год и Санта-Клаус уже начал готовить свою волшебную оленью упряжку, на которой он развозит подарки детям. Известно, что упряжку везут несколько волшебных оленей, на каждом из которых едут два эльфа.

Но волшебные олени — строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью a_i, а каждый эльф — темпераментом b_i. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо b_j < a_i < b_k, либо b_k < a_i < b_j.

Чтобы его появление было максимально зрелищным, Санта-Клаус хочет, чтобы в его упряжке было как можно больше оленей. Про каждого оленя Санта знает его строптивость, а про каждого эльфа — его темперамент.

Помогите Санте выяснить, какое максимальное количество оленей он сможет включить в упряжку, каких оленей ему следует выбрать, и какие эльфы должны на них ехать.

Формат входного файла

Первая строка входного файла содержит два целых числа m и n — количество оленей и эльфов, соответственно.

Вторая строка содержит m целых чисел a_i — строптивость оленей. Третья строка содержит n целых чисел b_i — темперамент эльфов.

Формат выходного файла

На первой строке выходного файла выведите одно число k — максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. На следующих k строках выведите по три целых числа: d_i, e_i,1, e_i,2 — для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входном файле.

Ограничения

Примеры тестов

4 6
2 3 4 5 
1 3 2 2 5 2

2
1 1 2
3 4 5

Задача B. Эксперимент ≡

Условие

Сегодня Игорь получил долгожданное разрешение на проведение эксперимента по изучению протекания химических реакций в магнитном поле. При этом используются две установки — генератор магнитного поля и манипулятор, соединяющий реагенты.

Эксперимент разбит на некоторое количество этапов, при этом некоторые из них могут быть выполнены только после завершения определенного набора других этапов. Правда известно, что хотя бы один способ проведения эксперимента существует. На каждом этапе Игорь должен управлять ровно одной из двух установок — либо генератором, либо манипулятором.

Игорь очень дорожит своим временем, и поэтому он хочет провести эксперимент, совершив наименьшее количество перемещений между пультами управления установками. Помогите ему узнать, в каком порядке следует выполнять этапы, чтобы этого добиться.

Формат входного файла

На первой строке входного файла записано целое число n — количество этапов эксперимента.

Следующие n строк содержат описание этапов. Пронумеруем этапы от 1 до n в некотором произвольном порядке. Тогда i-я из этих строк описывает i-й этап. Каждый этап описывается последовательностью целых чисел. Первое число равно нулю, если на этом этапе Игорь управляет генератором, и единице, если он управляет манипулятором. Затем записано целое число r_i — количество этапов, которые должны быть выполнены перед выполнением данного. За ним следуют номера этих этапов — r_i различных целых чисел в диапазоне от 1 до i − 1.

Формат выходного файла

Ограничения

Примеры тестов

3
1 0
0 0
1 2 1 2

1
2 1 3

Задача C. Планета Плюк ≡

Условие

На планете Плюк, поверхность которой мы будем считать абсолютно плоской, был разработан новый принцип перемещения единственного имеющегося там транспортного средства — пепелаца. А именно, на расстоянии одного километра друг от друга в точках (0, 0) и (1, 0) были построены две станции управления пепелацами A и B. С помощью них можно мгновенно переместить любой пепелац, повернув его на 90 градусов по или против часовой стрелки относительно точки A или B. Расстояние от пепелаца до соответствующей станции при этом не меняется. Следующее перемещение можно делать как относительно той же станции, так и относительно другой.

Например, если повернуть пепелац, находящийся в точке (3, 1) на 90 градусов против часовой стрелки относительно станции A, то он переместится в точку (−1, 3), если его затем повернуть на 90 градусов по часовой стрелке относительно станции B, то он переместится в точку (4, 2), если затем повернуть его вокруг станции B по часовой стрелке еще раз, он переместиться в точку (3, −3).

Один житель планеты недавно решил отправиться на своем пепелаце в гости к другу. Житель проживает около точки с координатами (x₁, y₁), а его друг — около точки с координатами (x₂, y₂). Помогите жителю с помощью станций управления пепелацем оказаться как можно ближе к месту, где проживает его друг, чтобы потом меньше было идти по пустыне.

Поскольку перемещения мгновенные и абсолютно бесплатные, то минимизировать количество перемещений не надо.

Формат входного файла

Входной файл содержит четыре целых числа — x₁, y₁, x₂ и y₂, они не превышают 10⁴ по абсолютной величине.

Формат выходного файла

Выведите в выходной файл последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки (x₁, y₁) как можно ближе к точке (x₂, y₂).

Поворот по часовой стрелке относительно станции A обозначается как "+A", поворот против часовой стрелки относительно станции A обозначается как "-A", соответствующие повороты относительно станции B обозначаются как "+B" и "-B". Выводите по одному перемещению на строке.

Выведенная последовательность не обязана быть минимальной по количеству перемещений, но должна содержать не более 10⁶ действий.

Примеры тестов

3 1
3 -3

-A
+B
+B

0 0
3 0

-B
-B