Язык программирования

Дано натуральное число N. Рассмотрим его разбиение на натуральные слагаемые. Два разбиения, отличающихся только порядком слагаемых, будем считать за одно, поэтому можно считать, что слагаемые в разбиении упорядочены по невозрастанию.

Входные данные
Задано единственное число N. (N ≤ 40)

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

Примеры

№	Входные данные	Выходные данные
1	5	1 1 1 1 1  2 1 1 1  2 2 1  3 1 1  3 2  4 1  5

У нас есть сетка с H строками и W столбцами. Квадрат в i-й строке и j-м столбце будет называться Square(i, j). Целые числа от 1 до H·W записаны по всей сетке, а целое число, записанное в Square(i, j), равно Ai,j.
Вы - волшебник (волшебница), и можете телепортировать фигуру, помещенную на Square(i, j) в Square(x, y), потратив \(|x-i|+|y-j|\) маджиков (магических монет).
Теперь вам нужно пройти Q практических тестов на свои способности как волшебника (волшебницы). I-е испытание будет проводиться следующим образом:
- первоначально фигура располагается в квадрате, где записано целое число Li;
- пусть x будет целым числом, записанным в квадрате, занятом фигурой. Неоднократно переместите фигуру в квадрат, где написано целое число x+D, пока x не станет равен Ri. Тест заканчивается, когда x = Ri .
Гарантируется, что Ri- Li делится на D.
Для каждого теста найдите сумму маджиков, израсходованных во время этого теста.

Входные данные
В первой строке заданы три целых числа: H, W и D (\(1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
В следующих H строках записано по W чисел Ai,j (\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))\).
В следующей строке записано целое число Q (\(1 \leq Q \leq 10^5\)).
В последних Q строках записано по 2 целых числа: Li и Ri (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) кратно D.

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 3 2 1 4 3 2 5 7 8 9 6 1 4 8	5	- 4 записано Square (1,2). - 6 записано в Square (3,3). - 8 записано in Square (3,1). Таким образом, сумма магических очков, израсходованных во время одного теста, составляет:  \((|3-1|+|3-2|)+(|3-3|+|1-3|)=5\).
2	4 2 3 3 7 1 4 5 2 6 8 2 2 2 2 2	0 0	Обратите внимание, что может быть тест, в котором фигура вообще не перемещается, и может быть несколько идентичных тестов.
3	5 5 4 13 25 7 15 17 16 22 20 2 9 14 11 12 1 19 10 6 23 8 18 3 21 5 24 4 3 13 13 2 10 13 13	0 5 0

 

Дан набор из N элементов. Значение i-го элемента (\(1<=i<=N\)) равно vi. Из данного набора выбирается не менее A и не более B элементов. Найти максимально возможное среднее арифметическое значений выбранных элементов. Кроме того, найти количество способов выбора элементов, чтобы среднее значение выбранных элементов было максимальным.

Входные данные
В первой строке задается три целых числа через пробел: N (\(1<=N<=50\)), A и B (\(1<=A,B<=N\)). В следующих N строках записаны целые числа vi (\(1<=v_i<=10^{15}\)), по одному числу в строке.

Выходные данные
Выведите две строки.
Первая строка должна содержать максимально возможное среднее арифметическое значений выбранных элементов. Вывод следует считать правильным, если абсолютная или относительная погрешность не превышает \(10^{-6}\). 
Вторая строка должна содержать количество способов выбора элементов, чтобы среднее значение выбранных элементов было максимальным.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	5 2 2 1 2 3 4 5	4.500000 1	Среднее значение выбранных элементов будет максимальным при выборе четвертого и пятого элементов. Следовательно, первая строка вывода должна содержать 4.5. Нет другого способа выбрать элементы, чтобы среднее значение было 4,5, и поэтому вторая строка вывода должна содержать 1.
2	4 2 3 10 20 10 10	15.000000 3	Может быть несколько способов выбора элементов, чтобы среднее значение было максимальным.
3	5 1 5 1000000000000000 999999999999999 999999999999998 999999999999997 999999999999996	1000000000000000.000000 1

 

Дано целое число N (\(1<=N<=10^{10}\)).
Для двух положительных целых чисел A и B определим \(F (A, B)\) как большее из двух: 
- количество цифр в десятичной записи числа A;
- количество цифр в десятичной записи числа B.
Например, \(F (3,11) = 2\), поскольку 3 состоит из одной цифры, а 11 - из двух.
Найдите минимальное значение \(F (A, B)\) среди всех пар положительных целых чисел A и B, таких что \(N = A \cdot B\).

Входные данные
На вход подается целое число N (\(1<=N<=10^{10}\)).

Выходные данные
Выведите на экран ответ на задачу.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10000	3	\(F(A,B) \) имеет минимальное значение при \((A,B)=(100,100)\).
2	1000003	7	Есть две пары A и B, таких чтобы выполнялость условие задачи: \((1,1000003)\) и \((1000003,1)\). Для этих пар, \(F(1,1000003)=F(1000003,1)=7\).
3	9876543210	6

 

План эвакуации из здания нарисован в виде плоскости xy. В здании N кабинетов и M лестниц, ведущих к выходу. Координаты i-го кабинета (\( 1<=i<=N\)) - \((a_i, b_i)\), а координаты лестниц с номером j (\( 1<=j<=M\)) - \((c_j, d_j)\). Во время пожарной тревоги, все люди, находящиеся в конкретном кабинете должны эвакуироваться по ближайшей лестнице. Ближайшая лестница определяется по Манхэттенскому расстоянию между двумя точками \((x_1, y_1)\) и \((x_2, y_2)\) по формуле \(|x_1-x_2| + |y_1-y_2|\). Здесь \(|x|\) обозначает абсолютное значение x. Если для кабинета есть несколько ближайших лестниц, то эвакуироваться необходимо по лестнице с наименьшим индексом. 
Определите по какой лестнице должны эвакуироваться люди, находящиеся в каждом кабинете.

Входные данные
В первой строке задаются два целых числа N и M (\(1<=N,M<=50\)).   Далее идет N строк по два целых числа в кажой строке - координаты \((a_i, b_i)\), затем M строк по два целых  числа в кажой строке - координаты \((c_i, d_i)\). \(-10^8<=a_i ,b_i,c_j,d_j<=10^8\). 

Выходные данные
Выведите N строк. В i-й строке (\( 1<=i<=N\)) должен быть указан индекс лестницы, по которой эвакуируются из i-го кабинета.
 

 

Примеры

№	Входные данные	Выходные данные
1	2 2 2 0 0 0 -1 0 1 0	2 1
2	3 4 10 10 -10 -10 3 3 1 2 2 3 3 5 3 5	3 1 2
3	5 5 -100000000 -100000000 -100000000 100000000 100000000 -100000000 100000000 100000000 0 0 0 0 100000000 100000000 100000000 -100000000 -100000000 100000000 -100000000 -100000000	5 4 3 2 1

 

Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи N одинаковых товаров и получи еще один товар бесплатно"и "купи K товаров по цене K−1 товара".

Для проведения олимпиады организаторам требуется распечатать условия для участников, на что уходит очень много бумаги. Каждая пачка стоит B рублей. Какое максимальное количество пачек бумаги можно приобрести на A рублей, правильно используя рекламные предложения?

Входные данные
Во входном файле записаны целые числа N, K, A и B (1 ≤ N ≤ 100, 2 ≤ K ≤ 100, 1 ≤ A ≤ 10⁹, 1 ≤ B ≤ 10⁹), разделенные пробелами.

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

Примечание
В первом примере, дважды используя второе рекламное предложение, можно купить 8 пачек бумаги, заплатив за 6.

Во втором примере рекламными предложениями воспользоваться нельзя.

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

Примеры

№	Входные данные	Выходные данные
1	4 4 13 2	8
2	3 4 8 3	2
3	3 4 7 1	9

Громозека собирается принять участие в финальном раунде STCoder Contest. В этом соревновании N задач, пронумерованных от 1 до N. Громозека знает, что на  решение задачи i (\(1<=i<=N\)) требуется Ti секунд. Кроме того, участникам предлагается M видов напитков, пронумерованных от 1 до M. Если Громозека выпьет напиток i (\(1 <= i <= M\)), его мозг будет стимулироваться и время, необходимое ему для решения задачи Pi станет Xi секунд. Это не влияет на время решения других задач.
Участнику разрешается выпить ровно один из напитков до начала конкурса. Для каждого напитка Громозека хочет знать, сколько секунд ему понадобится, чтобы решить все задачи, если он выпьет этот напиток. Предположим, что время, необходимое ему для решения всех задач, равно сумме времени, необходимого для решения отдельных задач. Ваша задача - написать вместо Громозеки программу для расчета времени.

Входные данные
На вход подаются целые числа. В первой строке число N (\(1<=N<=100\)), во второй строке N чисел Ti (\(1<=T_i<=10^5\)). В третьей строке задано число M (\(1<=M<=100\)). Далее идет M строк, в каждой из которых задана пара Pi,Xi (\(1<=P_i<=N\), \(1<=X_i<=10^5\)).


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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 2 1 4 2 1 1 2 3	6 9	Если Громозека выпьет напиток под номером 1, время, необходимое ему для решения каждой задачи, составит 1, 1 и 4 секунды, соответственно, всего 6 секунд. Если Громозека выпьет напиток 2, время, необходимое ему для решения каждой задачи, составит 2, 3 и 4 секунды, соответственно, всего 9 секунд.
2	5 7 2 3 8 5 3 4 2 1 7 4 13	19 25 30

 

У Громозеки есть любимая строка S, состоящая из строчных английских букв и пустая строка T. В конец строки T он хочет добавить произвольное количество раз одно из следующих слов: dream, dreamer, erase и eraser. Помогите Громозеке определить, сможет ли он получить S = T.

Формат входных данных
На вход подается строка S (1<= длина строки S <=10⁵), состоящая из строчных английских букв (a-z).

Формат выходных данных
Если возможно получить S = T, выведите YES. В противном случае выведите NO.

 

Дана последовательность из N целых чисел (они могут быть положительными, отрицательными или равными 0). Необходимо выбрать из этих чисел два числа так, чтобы их произведение было как можно меньшим (не рассматриваются квадраты данных чисел, но можно выбрать произведение двух различных элементов последовательности, равных друг другу).
В первой строке входных данных записано целое число N, 2 ≤ N ≤10⁵ – количество данных чисел. Следующие N строк содержат сами числа, не превосходящие по модулю 40 000.
Программа должна вывести единственное целое число – наименьшее возможное произведение двух различных элементов этой последовательности.

Примеры

№	Входные данные	Выходные данные
1	3 1 -3 2	-6

Для пополнения бюджета в стране Авалон, известной своими горными туристическими маршрутами, ввели новый налог для туристов. Величина налога
пропорциональна длине маршрута, но, поскольку маршрут проходит по горам и пройденное расстояние, зависящее от высоты спуска и подъёма, подсчитать сложно, налог считается без
учёта высоты, то есть величина налога пропорциональна горизонтальному перемещению, совершённому туристической группой. Кроме того, в силу старинного обычая все
туристические группы должны перемещаться по горам Авалона строго с запада на восток. Турфирма хочет сэкономить на налоге, поэтому она хочет разработать туристический
маршрут с минимальной величиной налога. При этом, поскольку маршрут является горным, он должен содержать подъём в гору и спуск с горы, то есть на маршруте должна быть точка,
которая находится строго выше начала и конца маршрута. 
Турфирма составила карту гор Авалона, содержащую информацию о высоте гор при передвижении с запада на восток. Высоты гор измерены в точках через равные расстояния. 
Найдите на данной карте гор Авалона туристический маршрут минимальной длины, удовлетворяющий условию наличия подъёма и спуска.
Первая строка входных данных содержит число N – количество точек на карте гор Авалона. Следующие N строк содержат информацию о высоте гор в данных N точках при движении с запада на восток. Все числа натуральные, не превосходящие 10⁵.
Программа должна вывести два числа – номер точки начала маршрута и номер точки окончания маршрута. Точки нумеруются от 1 до N. Если маршрута, удовлетворяющего
условиям, не существует, программа должна вывести одно число 0.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 18 10 15 20 20 10 3	3 6	Дано 7 точек с высотами 18, 10, 15, 20, 20, 10, 3. Самый короткий маршрут, содержащий подъём и спуск, – это 15, 20, 20, 10. Он начинается в точке номер 3 и заканчивается в точке номер 6.
2	3 9 8 5	0	Высота гор монотонно убывает, поэтому искомого маршрута не существует.

Антонин, Бальбин и Цезарь играют в игру "Карты на троих", алгоритм которой следующий:
- сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт. На каждой карточке написана буква a, b или c. Порядок карт в колодах не может быть изменен;
- игроки ходят по очереди. Антонин ходит первым;
- если в колоде текущего игрока есть хотя бы одна карта, ему необходимо сбросить верхнюю карту в колоде;
- следующий ход переходит к игроку, имя которого начинается с буквы на сброшенной карте (a - Антонин, b - Бальбин, c - Цезарь);
- если колода текущего игрока пуста, игра заканчивается, и текущий игрок выигрывает игру.
Вам выдаются начальные колоды игроков (Sa, Sb, Sc). Состояние колоды Антонина записано в строке Sa, где i-й (\(1<=i<=len(S_a)\)) символ это буква в i-й карты в колоде. Строка Бальбина (Sb) и строка Цезаря (Sс) описываются таким же образом. 
Определите победителя в игре.

Формат входных данных
На вход подаются три ненулевых строки Sa, Sb и Sc, каждая с новой строки. Длина каждой строки не более 100 символов. Каждая строка состоит только из букв a, b или c.

Формат выходных данных
Если выиграл Антонин. то выведите букву A, если Бальбин - букву B, если Цезарь - букву C.

Примечание 
В первом тестовом примере игра будет развиваться следующим образом:
Антонин сбрасывает верхнюю карту своей колоды, a. Антонин делает следующий ход.
Антонин сбрасывает верхнюю карту своей колоды, с. Цезарь следующий.
Цезарь сбрасывает верхнюю карту своей колоды, с. Цезарь следующий.
Цезарь сбрасывает верхнюю карту своей колоды: a. Антонин делает следующий ход.
Антонин сбрасывает верхнюю карту своей колоды: a. Антонин делает следующий ход.
Колода Антонина пуста. Игра заканчивается, и Антонин выигрывает игру.

 

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

Формат входного файла
В первой строке задается N — количество звезд на небе (3  ≤ N ≤ 300000). В каждой из следующих N строк заданы целые X, Y (|X, Y| ≤  10⁹) — координаты соответствующей звезды.

Формат выходного файла
Выведите ответ к задаче.
 

Примеры

№	Входные данные	Выходные данные
1	3 0 0 1 0 0 1	1
2	4 0 0 1 0 0 1 1 1	4

Бесконечную таблицу, строки и столбцы которой пронумерованы целыми числами начиная с 1 сверху вниз и слева направо, заполняют целыми числами 1, 2, 3 и т.д. Числа выписываются в
соседние клетки по границам квадратов увеличивающегося размера (см. рисунок).


Формат входных данных
Программа получает на вход одно целое число n, 1 ≤ n ≤ 10¹⁸
Формат выходных данных
Программа должна вывести два целых числа: номер строки и номер столбца, в которых находится число n в этой таблице. Запись выводимых чисел должна содержать только цифры, вывод
действительных чисел в ответе считается неверным.

Примеры

№	Входные данные	Выходные данные
1	15	4 2

Количество конструкторов, которые может определить класс, равно?
A) 1
B) 2
C) Любое число
D) Ни один из упомянутых

Какое из следующих утверждений о конструкторах верно?

1. Если мы предоставляем конструктор с одним аргументом, то компилятор по-прежнему предоставляет конструктор без аргументов.
2. Статические конструкторы могут использовать необязательные аргументы.
3. Перегруженные конструкторы не могут использовать необязательные аргументы.
4. Если мы не предоставляем конструктор, компилятор предоставляет конструктор без аргументов.

Вожди известного племени Мумба-Юмба решили придумать новый боевой вопль для своих воинов. При этом они решили, что вопль должен состоять ровно из N букв (всего в алфавите племени M букв). Также, после долгих исследований было выяснено, что если в вопле встречается слово s_i  (слово – это последовательность букв алфавита, не длиннее трех символов), то этот вопль вселяет во врага f_i единиц страха. Если в вопль входит несколько слов, то их “страшность” суммируется. Например, если вопль содержит слова s_i и s_j, то вопль вселяет f_i+f_j единиц страха. 
Требуется по заданным N, M, алфавиту и списку слов s_i составить максимально страшный вопль. 

Входные данные:
В первой строке записано три числа – N, M и К (0<N≤100, 0<M<25, 0 ≤ K ≤ 100), где K – количество страшных слов. В следующей строке записан алфавит – строка из M строчных латинских букв. Далее в K строках записана информация о словах – само слово и через пробел одно число, обозначающее страшность этого слова (0 < f_i ≤ 10000).

Выходные данные:
В выходной файл необходимо вывести страшность полученного вопля и на следующей строке – сам вопль.

Примеры

№	Входные данные	Выходные данные
1	3 5 4 abcde abc 10 ab 5 be 7 e 4	16 abe

Мальчика Мишу с юных лет волновали вопросы доставки воды. Когда Мише было четыре года, он приносил воду для полива растений в воздушных шариках вместо вёдер, так как воду в ведре было проще расплескать. Когда Мише исполнилось шесть лет, он построил в квартире водопровод из трубочек для сока, автоматизировав тем самым поливку цветов у себя в комнате. Все полученные в школе знания Миша сразу же использовал в своих смелых изобретениях: передача воды по проводам, насос из зубочисток, кран из маминого флакончика духов — вот далеко не полный список изобретений мальчика в школьные годы.

Как известно, любому таланту надо дать возможность реализоваться, поэтому мама Миши отправила сына на инновационную олимпиаду по ирригации (ИОИ). На этой олимпиаде школьники со всех концов Берляндии соревнуются в умении доставить воду для поливки растений самыми причудливыми способами. Зная список изобретений Миши, несложно догадаться, что проведение подобной олимпиады весьма затратно, поэтому спустя n первых проведений олимпиады было решено ввести правило, по которому будет определяться место проведения соревнования в следующий год. Город для проведения олимпиады выбирается следующим образом: всего в Берляндии есть m городов, пронумерованных от 1 до m, готовых принять соревнование. Каждый год олимпиада проводится в городе, в котором она проводилась наименьшее число раз. Если таких городов несколько, то олимпиада проводится в городе с наименьшим номером среди городов с минимальным числом проведений олимпиады.

Мишина мама очень волнуется за сына, поэтому её интересует, в каком городе будет проходить олимпиада в определённые годы. Единственная информация, которой располагает мама Миши, — места проведения олимпиады в первые n лет. Помогите маме Миши, и она попросит Мишу не залить вашу квартиру.

Входные данные
В первой строке заданы три целых числа n, m и q (1 ≤ n, m ≤ 500000 , 1 ≤ q ≤ 20) — количество проведений олимпиады до введения правила, количество городов в Берляндии, готовых провести олимпиаду, и число лет, про которые маму Миши интересует место проведения олимпиады, соответственно.

В следующей строке содержится n целых чисел a_i (1 ≤ a_i ≤ m) — номера городов, в которых проводилась олимпиада в год i. Обратите внимание, что до принятия правила место проведения олимпиады могло выбираться произвольным образом.

В следующих q строках заданы целые числа k_i (n+1 ≤ k_i ≤ 10¹⁸) — номера годов, для которых маму Миши интересует место проведения олимпиады.

Выходные данные
Выведите q целых чисел. В строке с номером i выведите одно целое число — место проведения олимпиады в год k_i.

Примеры

№	Входные данные	Выходные данные
1	6 4 10 3 1 1 1 2 2 7 8 9 10 11 12 13 14 15 16	4 3 4 2 3 4 1 2 3 4
2	4 5 4 4 4 5 1 15 9 13 6	5 3 3 3

Иннокентий работает на блошином рынке, продавая посетителям всякий хлам необычные вещи. Недавно он нашёл у себя на складе старое прямоугольное покрывало. Как оказалось, это покрывало имеет сетчатую форму, то есть покрывало состоит из nm цветных лоскутков, разбитых на n строк и m столбцов.

Цветные лоскутки привлекли внимание Иннокентия, и он сразу же придумал, как можно заработать на своей находке. Если вырезать из покрывала подпрямоугольник, состоящий из трёх цветных полос, то потом этот подпрямоугольник можно будет продать как флаг какой-нибудь страны. В частности, Иннокентий считает, что подпрямоугольник будет достаточно похож на флаг какой-нибудь страны, если он будет состоять из трёх одноцветных полос одинаковой высоты, находящихся друг под другом. Разумеется, цвет верхней полосы не должен совпадать с цветом средней полосы, а цвет средней не должен совпадать с цветом нижней.

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



Входные данные
Первая строка содержит два целых числа n и m (1 ≤ n, m ≤ 1000 ) — количество строк и столбцов в покрывале.

Каждая из следующих n строк описывает очередную строку покрывала и состоит из m строчных латинских букв от « a » до « z », где одинаковым цветам соответствуют одинаковые буквы, а разным цветам — разные буквы.

Выходные данные
В единственной строке выведите одно целое число — количество подпрямоугольников, являющихся флагами.

Примечание

Примеры

№	Входные данные	Выходные данные
1	4 3 aaa bbb ccb ddd	6

Дано верное равенство вида a₁+a₂+…+a_N=b₁+b₂+…b_M, где a₁,a₂,…,a_N, b₁,b₂,…,b_M – некоторые действительные (не обязательно целые) числа. Требуется «округлить» это равенство, т.е. получить новое верное равенство c₁+c₂+…+c_N=d₁+d₂+…+d_M, где c₁,c₂,…,c_N,d₁,d₂,…,d_M — целые числа, и при этом c₁ получено округлением числа a₁ до целого вверх или вниз (так, например, число 1.7 разрешается округлить как до 1, так и до 2), c₂ получено округлением a₂, …, c_N – округлением a_N, d₁ – округлением b₁, …, d_M – округлением b_M. Если какое-то из чисел в исходном равенстве было целым, оно должно остаться без изменений.

Входные данные
Во входном файле задано сначала число N, затем N чисел a₁, a₂, …, a_N, затем число M, затем числа b₁, b₂, …, b_M. Каждое число задается на отдельной строке. M и N – натуральные числа, не превышающие 1000. Остальные числа — вещественные, каждое из них по модулю не превышает 1000 и содержит не более 6 цифр после десятичной точки. При этом a₁+a₂+…+a_N=b₁+b₂+…b_M.

Выходные данные
Если «округлить» равенство можно, то в выходной файл выведите сначала числа c₁,c₂,…,c_N, а затем числа d₁,d₂,…,d_M. Все числа должны быть целыми и выведены без десятичной точки. Числа должны разделяться пробелами или переводами строки. Если решений несколько, выведите любое из них.

Если округлить исходное равенство до верного целочисленного равенства невозможно, выведите одно число 0.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 0.15 -3.000 2.7 1 -0.15	1 -3 2 0	Обратите внимание, что число –3 может округляться только в –3, в то время как 0.15 можно округлить как до 0, так и до 1, 2.7 – до 2 или до 3, –0.15 – до –1 или до 0. Приведенное решение не является единственным: так же верным является, например, такое округление: 1+(–3)+2=0
2	2 1.7 2.5 3 1 2.000 1.20	2 2 1 2 1	Приведенное решение 1+3=1+2+1 не является единственным. Верными ответами также являются 2+2=1+2+1 и 2+3=1+2+2.
3	1 0.5 1 0.5	0 0	Здесь верными являются как ответ 1=1, так и 0=0.

Напишите программу, которая по изображению поля для игры в «Крестики-нолики» определит, могла ли такая ситуация возникнуть в результате игры с соблюдением всех правил.

Напомним, что игра в «Крестики-нолики» ведется на поле 3×3. Два игрока ходят по очереди. Первый ставит крестик, а второй – нолик. Ставить крестик и нолик разрешается в любую еще не занятую клетку поля. Когда один из игроков поставит три своих знака в одной горизонтали, вертикали или диагонали, или когда все клетки поля окажутся заняты, игра заканчивается.

Входные данные
Вводится три строки по три числа в каждой, описывающих игровое поле. Число 0 обозначает пустую клетку, 1 – крестик, 2 – нолик. Числа в строке разделяются пробелами.

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

Примеры

№	Входные данные	Выходные данные
1	1 1 1 1 1 1 1 1 1	NO
2	2 1 1 1 1 2 2 2 1	YES
3	1 1 1 2 0 2 0 0 0	YES
4	0 0 0 0 1 0 0 0 0	YES
5	1 1 1 2 2 2 0 0 0	NO