Алгоритмы

Имеется сетка из N строк и N столбцов квадратов. Пусть (i, j) индексы клетки, которая расположена в i-й строке сверху и j-м столбце слева. Эти клетки должны быть окрашены в один из цветов C от цвета 1 до цвета C. Первоначально (i, j) окрашен в цвет ci,j. Назовем сетку хорошей, когда выполняются следующие условия для всех i, j, x, y, удовлетворяющих \(1<=i,j,x,y<=N\):
- если \((i+j)\%3=(x+y)\%3\), цвет (i, j) и цвет (x, y) совпадают;
- если \((i+j)\%3\neq(x+y)\%3\), цвет (i, j) и цвет (x, y) различны.
Здесь \(X \% Y \) представляет X по модулю Y.
Мы перекрасим ноль или более клеток, чтобы сетка была хорошей сеткой.
Неправильной клеткой назовем клетку, которая имела цвет X до перерисовки и Y после перекраски (DX,Y).
Найдите минимально возможную сумму всех неправильных клеток.

Входные данные
В первой строке задаются два целых числа N и C. В следующих C строках задаются по C значений Di,j. В последних N строках записаны N чисел в каждой строке - ci,j.

Выходные данные
Выведите минимально возможную сумму всех неправильных клеток
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 3 0 1 1 1 0 1 1 4 0 1 2 3 3	3	Перекрасить (1,1) в цвет 2. Неправильный (1,1) становится D 1,2 = 1. Перекрасить (1,2) в цвет 3. Неправильность (1,2) становится D 2,3 = 1. Перекрасить (2,2) в цвет 1. Неправильность (2,2) становится D. 3,1 = 1. В этом случае сумма неправильности всех квадратов равна 3. Отметим, что возможно \(Di, j  \neq D j, i \).
2	4 3 0 12 71 81 0 53 14 92 0 1 1 2 1 2 1 1 2 2 2 1 3 1 1 2 2	428

 

Чтобы затруднить снятие денег, банк на планете Крокрыс разрешает своим клиентам снимать только одну из следующих сумм за одну операцию:
- 1 крокрыскоин (действующая монета на планете Крокрыс);
- 6 крокрыскоинов, 36 (=6²) крокрыскоинов, 216(=6³) крокрыскоинов , ...;
- 9 крокрыскоинов, 81 (=9²) крокрыскоинов, 729(=9³) крокрыскоинов , ...
Сколько минимум операций требуется, чтобы вывести ровно N крокрыскоинов?
Невозможно повторно внести снятые вами деньги.

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

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	127	4	При снятии 1 + 9 + 36 + 81 получится снять 127 крокрыскоина за 4 операции.
2	3	3	1+1+1 = 3, всего 3 операции
3	44852	16

 

Напишите программу, переводящую число из двоичной системы счисления в шестнадцатеричную

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

Выходные данные
Необходимо записать в шестнадцатеричном виде и вывести данное число с использованием цифр 0, ..., 9 и букв A, ..., F без лидирующих нулей.

Примеры

№	Входные данные	Выходные данные
1	10100	14

У нас есть сетка с 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-го человека - Si . Мы хотим выбрать трех человек, чтобы выполнялись следующие условия:
- имя каждого выбранного человека начинается с M, А, R, С или Н; 
- среди выбранных людей нет людей, имена которых начинаются с одной буквы.
Сколько существует таких способов выбрать трех человек, не обращая внимания на порядок?

Входные данные
В первой строке записано целое число N (\(1<=N<=10^5\)) В следующих N строках записаны имена Si - строка, состоящая только из английских заглавных букв, длина строки не более 10 символов. Все имена различные.

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 MASHIKE RUMOI OBIRA HABORO HOROKANAI	2	Трех людей можно выбрать такими способами: - MASHIKE, RUMOI, HABORO - MASHIKE, RUMOI, HOROKANAI Ответ: 2
2	4 ZZ ZZZ Z ZZZZZZZZZZ	0
3	5 CHOKUDAI RNG MAKOTO AOKI RINGO	7

Весельчак У любит дарить алмазных черепашек. У него в сумке лежат черепашки либо трех цветов: розовый, белый и зеленый, либо четырех цветов: розовый, белый, зеленый и желтый. Он по очереди дарил черепашек из сумки, цвет i-й черепашки был Si. Цвета представлены следующим образом: P - розовый, W - белый, G - зеленый, Y - желтый. Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

Входные данные
В первой строке записано число N (\(1<=N<=100\)) - количество Черепашек, которое вынимал Весельчак У. Во второй строке содержатся N символов Si - цвета, вынимаемых черепашек. Каждый символ Si равен P, W, G или Y. Всегда существуют такие i, j и k, что Si = 'P', Sj = 'W' и Sk = 'G'.

Выходные данные
Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

 

Примеры

№	Входные данные	Выходные данные
1	6 G W Y P Y W	Four
2	9 G W W G P W P G G	Three
3	8 P Y W G Y W Y Y	Four

У Громозеки есть N часов. Стрелка i-х часов (\(1<=i<=N\)) поворачивается на 360 ° ровно за Ti секунд. Изначально стрелка всех часов стоит на месте и направлена прямо вверх. Громозека запускает все часы одновременно. Через сколько секунд стрелка всех часов снова укажет прямо вверх?

Входные данные
В первой строке записано целое число N (\(1<=N<=100\)). В следующих N строках записаны целые числа Ti (\(1<=T_i<=10^{18}\)), по одному числу в строке. 

Выходные данные
Выведите на экран ответ. Гарантируется, что ответ не превышает \(10^{18}\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 2 3	6	У нас есть двое часов. Время, когда стрелка каждых часов указывает вверх, выглядит следующим образом: Часы 1: 2, 4, 6, ... секунд после начала. Часы 2: 3, 6, 9, ... секунд после начала. Таким образом, требуется 6 секунд, пока стрелки обоих часов снова не укажут прямо вверх.
2	5 2 5 10 1000000000000000000 1000000000000000000	1000000000000000000

 

Дано целое число 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

 

Пусть a₁ = 2, a₂ = 3, a_n = a_1·a₂·...·a_n-1 – 1 при n ≥ 3. Назовем числа ai псевдопростыми. Для заданного натурального числа X нужно ответить на вопрос: можно ли X однозначно представить в виде произведения псевдопростых чисел (представления, отличающиеся только порядком множителей, считаются одинаковыми), и, если можно — выдать разложение.<

Входные данные
Вводится одно натуральное число X, 1 < X ≤ 10⁹.

Выходные данные
Выведите псевдопростые числа, произведение которых равно X, в произвольном порядке. Если разложения не существует или оно не единственно, выдать 0.
 

Примеры

№	Входные данные	Выходные данные
1	6	2 3
2	5	5
3	7	0

Рассмотрим фигуру, аналогичную показанной на рисунке (большой равносторонний треугольник, составленный из маленьких равносторонних треугольников). На рисунке приведена фигура, состоящая из 4-х уровней треугольников.



Напишите программу, которая будет определять, сколько всего в ней треугольников (необходимо учитывать не только "маленькие" треугольники, а вообще все треугольники — в частности, треугольник, выделенный жирным, а также вся фигура, являются интересующими нас треугольниками).

Входные данные
Вводится одно число N — количество уровней в фигуре (1 ≤ N ≤ 100000).

Выходные данные
Выведите  количество треугольников в такой фигуре.

Примеры

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

Вновь открытое казино предложило оригинальную игру.

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

Рассмотрим пример. Пусть на столе выставлен ряд фишек rrrgggbbb, и крупье объявил последовательности rg и gb. Игрок, например, может забрать фишки rg, лежащие на третьем и четвёртом местах слева. После этого крупье сдвинет фишки, и на столе получится ряд rrggbbb. Ещё дважды забрав фишки rg, игрок добьётся того, что на столе останутся фишки bbb и игра закончится, так как игроку больше нечего забрать со стола. Игрок мог бы действовать и по-другому — на втором и третьем ходах забрать не последовательности rg, а последовательности gb. Тогда на столе остались бы фишки rrb. Аналогично, игрок мог бы добиться того, чтобы в конце остались ряды rrr или rbb.

После окончания игры полученные фишки игрок меняет на деньги. Цена фишки зависит от её цвета.

Требуется написать программу, определяющую максимальную сумму, которую сможет получить игрок.

Входные данные
В первой строке входных данных содержится число K (1 ≤ K ≤ 26) — количество цветов фишек. Каждая из следующих K строк начинается со строчной латинской буквы, обозначающей цвет. Далее в той же строке через пробел следует целое число X_i (1 ≤ X_i ≤ 150, i = 1..K) — цена фишки соответствующего цвета.

В (K+2)-ой строке описан ряд фишек, лежащих на столе в начале игры. Ряд задаетсяL строчными латинскими буквами (1 ≤ L ≤ 150), которые обозначают цвета фишек ряда.

В следующей строке содержится число N(1 ≤ N ≤ 150) — количество последовательностей, которые были объявлены крупье. В следующих N строках записаны эти последовательности. Гарантируется, что сумма длин этих N строк не превосходит 150 символов, и все они непустые.

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

Примеры

№	Входные данные	Выходные данные
1	3 v 3 l 1 u 2 luvu 3 luv vul uuu	6

Группа школьников решила сходить в поход вдоль Москвы-реки. У Москвы-реки существует множество притоков, которые могут впадать в нее как с правого, так и с левого берега.

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

Школьники заранее изучили карту и записали, в какой последовательности в Москву-реку впадают притоки на всем их маршруте.

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

Входные данные
Единственная строка содержит описание Москвы-реки между начальной и конечной точкой похода. Длина строки не превосходит 10⁵ символов.

Каждый символ строки может быть одной из трех латинских букв L, R или B. Буква L означает, что очередной приток впадает в реку с левого берега, R - приток впадает в реку с правого берега и B - притоки впадают с обоих берегов реки в одном месте. Поход начинается на левом берегу перед описанной частью реки и заканчивается на правом берегу после описанной части.

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

Примечания
Рисунок к приведенному ниже примеру.

Примеры

№	Входные данные	Выходные данные
1	LLBLRRBRL	5

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

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

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10) - количество заданных Петей вопросов. Каждая из N последующих строк содержит описание четырех точек - четыре пары целых чисел X и Y (−100 ≤ X ≤ 100, −100 ≤ Y ≤ 100), обозначающих координаты точки.

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

Примеры

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

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

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

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

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 10⁵) - количество папок. Во второй строке записаны N целых чисел a₁, a₂, ..., a_N (0 ≤ a_i ≤ 10⁵) - количество дипломов в каждой из папок.

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

Примечание
В первом примере Иван может открыть и просмотреть папку 2 за 2 секунды и, не найдя там диплома, понять, что диплом находится в папке 1.

Во втором примере Иван за 2 секунды просмотрит папку 1, потом за 2 секунды просмотрит папку 4, а если ни в одной из них диплома не встретилось, он поймет, что диплом в папке 3.

Примеры

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

Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи 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

Алиса и капитан Буран играют в покер с одной картой. Однокарточный покер - это игра для двух игроков с игральными картами. Каждая карта в этой игре показывает целое число от 1 до 13 включительно. Сила карты определяется числом, написанным на ней, следующим образом:
Слабая 2 <3 <4 <5 <6 <7 <8 <9 <10 <11 <12 <13 <1 Сильная
В покер с одной картой играют следующим образом:
- Каждый игрок берет одну карту из колоды.
- Выбранная карта становится рукой игрока.
- Игроки раскрывают друг другу руки.
- Игрок с более сильной картой побеждает в игре.
- Если их карты одинаково сильны, игра заканчивается вничью.
Вы смотрите, как Алиса и капитан Буран играют в игру, и можете видеть их руки. Число, написанное на карточке Алисы, - A, а число, написанное на карточке капитана Бурана, - B.

Напишите программу для определения исхода игры.
 

Ушан решил сыграть шестигранным кубиком. На каждой из шести сторон изображено целое число от 1 до 6, а два числа на противоположных сторонах всегда в сумме дают 7. Ушан сначала кладет кубик на стол произвольной стороной вверх, а затем повторно выполняет следующую операцию. Поверните кубик на 90 ° в одном из следующих направлений: влево, вправо, вперед (кубик приблизится) и назад (кубик уйдет дальше), затем получите y очков, где y - это число, написанное на стороне, обращенной вверх.

Например, давайте рассмотрим ситуацию, когда сторона, показывающая 1, обращена вверх, ближняя сторона показывает 5, а правая сторона показывает 4, как показано на рисунке (исходное положение для нашего примера).
Если кубик повернуть вправо, как показано на рисунке, сторона, показывающая 3, будет обращена вверх. Если из исходного положения кубик повернуть влево, сторона, показывающая 4, будет смотреть вверх. Вверху будет сторона, показывающая 2, если кубик из исходного положения повернуть вперед, а сторона, показывающая 5, будет обращена вверх, если кубик повернуть назад из исходного положения.

Найдите минимальное количество операций, которое Ушан должен выполнить, чтобы набрать в сумме не менее x баллов.

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

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

 

Примеры

№	Входные данные	Выходные данные
1	7	2
2	149696127901	27217477801

 

На линии, идущей с востока на запад, есть N городов. Города пронумерованы от 1 до N в порядке с запада на восток. Каждая точка на линии имеет одномерные координаты, а точка, которая находится дальше на восток, имеет большее значение координаты. Координата города i - Xi. Вы находитесь в городе 1 и хотите посетить все остальные города. У вас есть два способа путешествовать:
- Ходить по линии. Ваш уровень усталости увеличивается на A каждый раз, когда вы путешествуете на расстояние 1, независимо от направления.
- Телепортируйтесь в любое место по вашему выбору. Ваш уровень усталости увеличивается на B независимо от пройденного расстояния.
Найдите минимально возможное общее повышение уровня вашей усталости, когда вы посетите все города этими двумя способами.

Входные данные
В первой строке заданы три целых числа N (\(2<=N<=10^5\)), A (\(1<=A<=10^9\)), B (\(1<=B<=10^9\)). Во второй строке заданы координаты городов Xi (\(1<=X_i<=10^9\)), для всех i \(X_i <X_{i+1}\)(\(1<=i<=N-1\)).

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 2 5 1 2 5 7	11	Из города 1 пройдите расстояние 1 до города 2, затем телепортируйтесь в город 3, затем пройдите расстояние 2 до города 4. Общее увеличение вашего уровня усталости в этом случае составляет 2 × 1 + 5 + 2 × 2 = 11, что является минимально возможным значением.
2	7 1 100 40 43 45 105 108 115 124	84	Из города 1 пройдите пешком до города 7. Общее увеличение вашего уровня усталости в этом случае составляет 84, что является минимально возможным значением.
3	7 1 2 24 35 40 68 72 99 103	12	Посетите все города в любом порядке, телепортировавшись шесть раз. Суммарное повышение уровня утомляемости в этом случае составляет 12, что является минимально возможным значением.

 

Вам дано положительное целое число N (\(1<=N<=10^{18}\)). Найдите количество пар целых чисел u и v (\(0<=u, v<=N\)) таких, что существуют два неотрицательных целых числа a и b, удовлетворяющих \(a\ xor\ b=u\) и \(a+b=v\). Здесь xor обозначает побитовое исключающее ИЛИ. Поскольку ответ может быть очень большим, вычислите его по модулю \(10^9+7\).

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

Выходные данные
Выведите количество возможных пар целых чисел u и v (\(0<=u, v<=N\)) , по модулю \(10^9+7\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3	5	u=0,v=0 (Пусть a=0,b=0, тогда 0 xor 0=0, 0+0=0) u=0,v=2 (Пусть a=1,b=1, тогда 1 xor 1=0, 1+1=2) u=1,v=1 (Пусть a=1,b=0, тогда 1 xor 0=1, 1+0=1) u=2,v=2 (Пусть a=2,b=0, тогда 2 xor 0=2, 2+0=2) u=3,v=3 (Пусть a=3,b=0, тогда 3 xor 0=3, 3+0=3)
2	1422	52277
3	1000000000000000000	787014179

 

Есть N городов. Есть также шоссе K и железные дороги L, проходящие между городами. Каждое i-я шоссе двунаправленно соединяет рi и qi города, а каждая i-я железная дорога двунаправленно соединяет ri и si города. Нет двух шоссе, соединяющих одну и ту же пару городов. Точно так же, никакие две железные дороги не соединяют одну и ту же пару городов. Будем считать, что города A и B соединены шоссе, если до города B можно добраться из города A по некоторому количеству шоссе. Здесь любой город считается соединенным с собой шоссе. Аналогичным образом, мы также определим возможность сообщения железными дорогами. Для каждого города найдите количество городов, соединенных с этим городом как шоссе, так и железными дорогами.

Входные данные
Входные данные поступают в следующем формате:

N K L 
p1 q1 
...
pK qK 
r1 s1 
... 
rl sL

Ограничения:
\(2<=N<=2\cdot10^5 \\ 1<=K,L<=10^5 \\ 1<=p_i,q_i,r_i,s_i<=N\\ p_i <q_i \\ r_i<s_i \\ Когда\ i \neq j, (p_i,q_i)\neq(p_j,q_j) \\ ?Когда\ i \neq j, (r_i,s_i)\neq(r_j,s_j)\)


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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	4 3 1 1 2 2 3 3 4 2 3	1 2 2 1	Все четыре города связаны между собой дорогами. Железной дорогой соединены только второй и третий города. Таким образом, ответы для городов 1,2,2 и 1 соответственно.
2	4 2 2 1 2 2 3 1 4 2 3	1 2 2 1
3	7 4 4 1 2 2 3 2 5 6 7 3 5 4 5 3 4 6 7	1 1 2 1 2 2 2