Информатика

Последовательность Фибоначчи определяется так: \(f_0 = 0, f_1 = 1, ..., f_n = f_{n-1}+f_{n-2}\).

По данному числу n определите n-е число Фибоначчи fn.

Входные данные
Программа получает на вход натуральное число n.

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

Примеры

№	Входные данные	Выходные данные
1	6	8

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

Входные данные
Программа получает на вход два вещественных числа x и y.

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

Примеры

№	Входные данные	Выходные данные
1	10 20	9

Дано целое число, не меньшее 2. Выведите его наименьший натуральный делитель, отличный от 1.

Входные данные
На вход подается одно натуральное число.

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

Примеры

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

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

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

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

Примеры

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

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

Маленький Витя Ч., участвуя на своем первом в жизни соревновании, забыл сколько задач он решил. Витя Ч. помнит, что получил всего 10 оценок, а также сами оценки по порядку.
Определите сколько всего задач решил Витя Ч., за сколько задач он получил максимальный балл с первой попытки, а также общую сумму баллов, которую он набрал.


Входные данные
Программа получает 10 строк, в каждой из которых записано по одному неотрицательному числу от 0 до 5. 

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

Примеры

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

Существует сетка с H горизонтальными строками и W вертикальными столбцами. Пусть (i, j) обозначает квадрат в i-й строке сверху и в j-м столбце слева.
Найдите количество квадратов, которые имеют общую сторону с квадратом (R, C).

Квадрат (a, b) и квадрта (c, d), имеют одну общую сторону тогда и только тогда, когда |a-c|+|b-d|=1 (где |x| обозначает абсолютное значение x).

Входные данные
Програма получает на вход две строки. Первая строка содержит два целых числа H и W (1 <= H, W <= 10). Вторая строка содержит два целых числа R и C (1 <= H, W <= 10).

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

Примеры

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

Изображение сетки, для описанных выше примеров

Плитки выровнены по N горизонтальным строкам и N вертикальным столбцам. Каждая плитка имеет сетку с A горизонтальными рядами и B вертикальными столбцами. Все плитки образуют квадрат X с (A×N) горизонтальными строками и (B×N) вертикальными столбцами.
Для 1<= i, j<= N плитка (i, j) обозначает плитку в i-й строке сверху и в j-м столбце слева.

Каждый квадрат X окрашен следующим образом.

• Каждая плитка представляет собой либо белую плитку, либо черную плитку.
• Каждый квадрат в белой плитке окрашен в белый цвет; каждый квадрат в черной плитке окрашен в черный цвет.
• Плитка (1, 1) - это белая плитка.
• Две плитки, разделяющие одну сторону, имеют разные цвета. Плитка (a, b) и плитка (c, d), имеют одну общую сторону тогда и только тогда, когда |a-c|+|b-d|=1 (где |x| обозначает абсолютное значение x).

Распечатайте квадрат X в формате, указанном в формате.

Входные данные
Программа получает на вход три целых числа: N, A, B (1 <= N, A, B <= 10).

Выходные данные
Выведите на экран (A×N) строк S1,...,SAxN, которые удовлетворяют следующим условиям.
Каждая из строк S1,...,SAxN представляет собой строку длины (B×N), состоящую из . и #.
Для каждого значения i и j (1<= i <= A×N,1 <= j <= B×N) j-й символ строки Si является символом . ,если квадрат в i-й строке сверху и j-м столбце слева в квадрате X окрашен в белый цвет; символом #, если квадрат окрашен в черный цвет.
 
 

Примеры

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

Вам дан массив целых чисел А длиной n.
Необходимо ответить на m запросов вида "сообщите количество различных чисел подотрезка массива А от элемента с индексом l до элемента с индексом r" (обе границы подотрезка включены, массив нумеруется с единицы).

Входные данные:
В первой строке дано два числа: n - количество элементов массива и m - количество запросов (1 <= n, m <= 10⁵).
Во второй строке дано n целых чисел A_i - элементы массива (0 <= A_i <= 10⁶).
Далее дано m строк, в каждой по два числа l и r - границы подотрезка для каждого запроса (1 <= l <= r <= n).

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

Пример:
 

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

Есть набор строк, который изначально пуст. Необходимо обрабатывать три различные операции над этим набором строк:

• 1 s: Добавить данную строку в набор.
• 2 k l: Узнать, существуют ли в наборе k строк (не обязательно различных) таких, что они имеют общий суффикс длины l. Этот суффикс не обязан быть наибольшим.
• 3 i: Удалить строку из набора, которая была добавлена в i-й операции (если она еще не была удалена).

Входные данные:
В первой строке дано одно целое число - количество операций q (1 <= q <= 10⁵), которые необходимо обработать.
Далее в каждой строке дано описание запроса. Сперва это число 1, 2 или 3, обозначающее тип запроса. 
Если это запрос первого типа, то далее дана строка s, суммарная длина которых не превышает 10⁵.
Если это запрос второго типа, то далее дано два целых числа k и l (1 <= k, l <= 10⁵).
Если это запрос третьего типа, то далее дано число i (1 <= i <= номер текущей операции), где i - номер операции первого типа.

Выходные данные:
Для каждого запроса второго типа выведите в отдельной строке слово "YES", если существуют необходимые строки, и "NO" в противном случае.

Пример:
 

Входные данные	Выходные данные
9 1 aba 1 accba 2 2 2 2 2 3 1 aaaa 1 ababa 2 3 2 3 1 2 3 2	YES NO YES NO

В файле приведён фрагмент базы данных «Продукты» о поставках товаров в магазины районов города. База данных состоит из трёх таблиц.

Таблица «Движение товаров» содержит записи о поставках товаров в магазины в течение первой декады июня 2021 г., а также информацию о проданных товарах. Поле Тип операции содержит значение Поступление или Продажа, а в соответствующее поле Количество упаковок внесена информация о том, сколько упаковок товара поступило в магазин или было продано в течение дня. Заголовок таблицы имеет следующий вид.

ID операции

Дата

ID магазина

Артикул

Тип операции

Количество упаковок

Цена

Таблица «Товар» содержит информацию об основных характеристиках каждого товара. Заголовок таблицы имеет следующий вид.

Артикул

Отдел

Наименование

Единица измерения

Количество в упаковке

Производитель

Таблица «Магазин» содержит информацию о местонахождении магазинов. Заголовок таблицы имеет следующий вид.

ID магазина

Район

Адрес

На рисунке приведена схема указанной базы данных.


Используя информацию из приведённой базы данных, определите на какую сумму было получено риса всех сортов в магазинах Первомайского района за период со 1 по 3 июня включительно.

В ответе запишите только число.

Скачать файл
 

Эн идет в свой Грибной лес собирать грибы.

В Грибном лесу m ориентированных дорожек, соединяющих n деревьев. На каждой дорожке растут грибы. Когда Эн проходит по дорожке, он собирает все грибы на этой дорожке. Однако, в Грибном лесу такая плодородная почва, что грибы растут с фантастической скоростью. Новые грибы вырастают, как только Эн заканчивает собирать грибы на дорожке. А именно, после того, как Эн проходит по дорожке в i-й раз, вырастает на i грибов меньше, чем было до этого прохода. Таким образом, если на дорожке изначально было x грибов, то Эн соберет x грибов в первый проход, x - 1 гриб во второй, x - 1 - 2 гриба в третий и так далее. Однако, количество грибов не может стать меньше 0.
Например, пусть изначально на дорожке росло 9 грибов. Тогда количество грибов, которое соберет Эн, равно 9, 8, 6 и 3 для проходов с первого по четвертый. Начиная с пятого прохода и далее Эн ничего не сможет собрать с этой дорожки (но все еще может по ней ходить).

Эн решил начать от дерева s. Какое максимальное количество грибов он может собрать, передвигаясь только по описанным дорожкам?

Входные данные:
Первая строка содержит два целых числа n и m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — количество деревьев и количество ориентированных дорожек в Грибном лесу, соответственно.
Каждая из следующих m строк содержит три целых числа x, y и w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10⁸), описывающих дорожку, которая ведет от дерева x к дереву y с w грибами изначально. Возможны дорожки, которые ведут от дерева к нему же, а также несколько дорожек, соединяющих одну и ту же пару деревьев.
Последняя строка содержит одно целое число s (1 ≤ s ≤ n) — начальную позицию Эна.

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

Примеры:
 

Входные данные	Выходные данные
2 2 1 2 4 2 1 4 1	16
3 3 1 2 4 2 3 3 1 3 8 1	8

Пояснения:
В первом примере Эн может три раза пройти по кругу и собрать 4 + 4 + 3 + 3 + 1 + 1 = 16 грибов. После этого не будет грибов, которые Эн может собрать.
Во втором примере Эн может пойти к дереву 3 и собрать 8 грибов на дорожке от дерева 1 до дерева 3.

Дан граф из n вершин и m ориентированных ребер. В каждой вершине записана некоторая строчная латинская буква. 
Определим величину пути как наибольшее количество раз, которое какая-то буква встречалась на этом пути. Например, если буквы на пути образуют строку «abaca», то величина этого пути равна 3.
Ваша задача — найти путь с наибольшей величиной.

Входные данные:
Первая строка содержит два целых числа n, m (1 ≤ n, m ≤ 200000), означающих, что в графе n вершин и m ориентированных ребер.
Вторая строка содержит строку s, состоящую только из строчных латинских букв. Символ номер i — это буква, записанная в вершине номер i.
Далее следуют m строк. Каждая из этих строк содержит два целых числа x, y (1 ≤ x, y ≤ n), описывающих ориентированное ребро из x в y. Обратите внимание, x может быть равно y, и могут быть несколько ребер между x и y.
Кроме того, граф может быть несвязным.

Выходные данные:
Выведите одно число — максимальную величину пути. Если существуют пути со сколь угодно большой величиной, выведите -1.

Примеры:
 

Входные данные	Выходные данные
5 4 abaca 1 2 1 3 3 4 4 5	3
6 6 xzyabc 1 2 3 1 2 3 5 4 4 3 6 4	-1
10 14 xzyzyzyzqx 1 2 2 4 3 5 4 5 2 6 6 8 6 5 2 10 3 9 10 9 4 6 1 10 2 8 3 7	4

Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший путь
из вершины s в вершину t.

Входные данные:
Первая строка входного файла содержит четыре целых числа n, m, s и t - количество вершин, ребер графа, начальная и конечная вершина соответственно (1 <= n <= 100000; 0 <= m <= 200000; 1 <= s, t <= n).
Следующие m строк содержат описания ребер по одной на строке. 
Ребро номер i описывается тремя целыми числами b_i, e_i и w_i - началом, концом и длиной ребра соответственно (1 <= b_i, e_i <= n; |w_i| <= 1000). 
Граф не содержит циклов и петель.

Выходные данные:
Первая строка выходного файла должна содержать одно целое число - длину кратчайшего пути из s в t. 
Если пути из s в t не существует, выведите "Unreachable".

Примеры:
 

Входные данные	Выходные данные
2 1 1 2 1 2 -10	-10
2 1 2 1 1 2 -10	Unreachable

Кайману снится необычный сон, будто он попал в странный район города. Этот район можно представить как граф-дерево, где вершины - это перекрестки и ребра - двусторонние дороги, которые соединяют эти перекрестки. Всего перекрестков n и у каждого свой номер от 0 до n-1.

Но не все так плохо в этом сне, ведь на каждой дороге между перекрестками с номерами u и v есть С_u,v пельменей! Кайман очень любит пельмешки, поэтому хочет съесть как можно больше, но есть проблема - если он побывает в каком-либо перекрестке более чем k раз, то на него нападет злой пельменный монстр.

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

В начале сна Кайман находится на перекрестке с номером 0. Помогите ему определить, какое максимальное количество пельменей он сможет съесть, но так, чтобы на него не напал злой пельменный монстр.

Входные данные:
В первой строке следует два целых числа n и k (3 ≤ n ≤ 10⁵; 1 ≤ k ≤ 10⁵) — количество перекрестков и максимальное количество посещений каждого из перекрестков.
В следующих n - 1 строках следует по три целых числа u, v и C_u,v (0 ≤ u, v ≤ n - 1; 0 ≤ C_u,v ≤ 10000), означающих, что перекрестки с номерами u и v связаны дорогой, на которой C_u,v пельменей.
Гарантируется, что перекрестки и дороги формируют дерево.

Выходные данные:
Выведите одно целое число - максимальное количество пельменей, которое сможет съесть Кайман.

Примеры:
 

Входные данные	Выходные данные
9 3 0 1 1 0 2 1 1 3 2 1 4 2 1 5 2 2 6 3 2 7 3 2 8 3	15
9 5 0 1 1 0 2 1 1 3 2 1 4 2 1 5 2 2 6 3 2 7 3 2 8 3	17
11 6 1 0 7932 2 1 1952 3 2 2227 4 0 9112 5 4 6067 6 0 6786 7 6 3883 8 4 7137 9 1 2796 10 5 6200	54092

Пояснение:
В первом примере нужно посетить перекрестки в следующем порядке: 0, 1, 5, 1, 3, 1, 0, 2, 6, 2, 7, 2, 8. Тогда он съест суммарно 1+2+2+1+3+3+3 = 15 пельменей.
Обратите внимание, что ни один перекресток не посещается более чем 3 раза.
 

Сегодня в замке Эна проходит фестиваль пирогов, в котором участвуют n пекарен, каждая из которых имеет свой уникальный номер от 1 до n.
Некоторые пекарни соединены между собой двусторонними дорогами, но таким образом, что если из пекарни i можно дойти до пекарни j, то существует ровно один маршрут между ними.

Когда Эн ест пироги в i-й пекарне, то он получает A_i удовольствия. А если проходит по дороге между некоторыми пекарнями с номерами v и u, то вкусный аромат пирогов приносит Эну C_v,u удовольствия.

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

Помогите Эну определить максимально возможное удовольствие, которое он сможет получить.

Входные данные:
В первой строке дано число n (1 <= n <= 50000) - количество пекарен, и число k - количество существующих дорог между пекарнями.
Во второй строке дано n чисел A_i (0 <= A_i <= 10000) - удовольствие от пирогов i-й пекарне.
Далее следует k строк, в каждой по 3 числа v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), означающие, что существует дорога между пекарнями с номерами v и u, и аромат на этой дороге приносит C удовольствия.

Выходные данные:
Выведите одно число - максимально возможное удовльствие.

Примеры:
 

Входные данные	Выходные данные
2 1 1 1 1 2 1	3
8 7 1 5 4 6 10 1 2 2 1 2 1 2 3 10 2 4 1 4 5 1 4 6 2 6 7 2 6 8 3	37

Пояснения:
В первом примере нужно начать в 1-й пекарне (1 удовольствие), пройти по дороге между 1-й и 2-й пекарнями (1 удовольствие) и посетить 2-ю пекарню (1 удовольствие). Суммарное удовольствие - 1+1+1 = 3.
Во втором примере нужно начать в 5-й пекарне (10 удовольствия), пройти по дороге между 5-й и 4-й пекарнями (1 удовольствие), посетить 4-ю пекарню (6 удовольствия), пройти по дороге между 4-й и 2-й пекарнями (1 удовольствие), посетить 2-ю пекарню (5 удовольствия), пройти по дороге между 2-й и 3-й пекарнями (10 удовольствия), посетить 3-ю пекарню (4 удовольствия). Суммарное удовольствие - 10+1+6+1+5+10+4 = 37.

Вам дано дерево (связный ациклический неориентированный граф), состоящее из n вершин.
Найдите размер его максимального паросочетания (набор попарно несмежных ребер).

Входные данные:
В первой строке дано число n - количество вершин в дереве.
Далее идет n-1 строка, в каждой из которых дается по два числа a_i и b_i (1 <= a_i, b_i <= n) - ребра дерева.

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

Примеры:
 

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

Пояснение:
В максимальное паросочетание данного дерева будут входить ребра 1-2 и 3-4.

Мирко стал генеральным директором крупной корпорации. В компании работает N человек, которые пронумерованы числами от 1 до N, причем сам Мирко имеет номер 1. У всех работников, кроме Мирко, есть начальник. Начальник может иметь несколько подчиненных, но не более одного своего начальника.

Когда Мирко получает задание от инвесторов, он передает его своему подчиненному с наименьшим номером. Этот подчиненный также передает его своему подчиненному с наименьшим номером, и так далее, пока задание не перейдет несчастливому работнику без подчиненных, который должен его выполнить.
Этот работник получает 1 монету, его начальник получает 2 монеты, начальник этого начальника получает 3 монеты, и так далее. Потом тот, кто на самом деле сделал работу, осознает, насколько эта капиталистическая система несправедлива, и увольняется с работы.

Мирко получает задания до тех пор, пока в корпорации не останется всего один сотрудник — сам Мирко. Тогда он выполняет это задание, получает 1 монету и уходит из корпорации.

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

Входные данные:
Первая строка содержит одно натуральное число N (1 ≤ N ≤ 2·10⁵) — число сотрудников компании. Следующая строка содержит N-1 чисел a₂, a₃, ... a_n (1 ≤ a_i < i), a_i — номер начальника i-го сотрудника.

Выходные данные:
Выведите N чисел, i-е число должно означать, сколько монет получил i-й сотрудник.

Примеры:
 

Входные Данные	Выходные данные
3 1 1	5 1 1
5 1 2 2 4	13 8 1 3 1

Пояснения:

Далее приведено описание ко второму примеру.

Мирко отдает первое задание работнику 2, который передает его работнику 3, который выполняет задание. Таким образом, работник 3 получает одну монету, работник 2 — две монеты, а работник 1, сам Мирко, — три монеты. После этого работник 3 увольняется.
Мирко отдает второе задание работнику 2, который передает его работнику 4, который тут же передает задание работнику 5, который выполняет задание. После этого работник 5 получает одну монету, работник 4 — две монеты, работник 2 — три монеты, а Мирко — четыре монеты. Работник 5 увольняется.
После выполнения третьего задания работник 4 получает одну монету, работник 2 — две монеты, а Мирко — три монеты, после чего работник 4 увольняется.
После выполнения четвертого задания работник 2 получает одну монету, а Мирко — две монеты, после чего второй работник увольняется.
Наконец, пятое задание выполняет сам Мирко, получая за это одну монету, после чего процесс прекращается.

Суммарно Мирко получил 13 монет, работник 2 — 8 монет, работник 4 — 3 монеты, а работники 3 и 5 — одну монету.

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} – нет.

Перестановка {p₁, p₂, …, p_n} будет лексикографически меньше перестановки {q₁, q₂, …, q_n}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого p_j = q_j при j < i и p_i < q_i.

В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой – множество {9, 3, 6, 8}.

Требуется написать программу, позволяющую найти m-ую k-перестановку в этом порядке.

Входные данные
Входной файл в первой строке содержит три натуральных числа – n (1 ≤ n ≤ 16), m и k (1 ≤ m, k ≤ 10⁹). Вторая строка содержит n различных натуральных чисел, не превосходящих 10⁹. Все числа в строках разделены пробелом.

Выходные данные
В выходной файл необходимо вывести m-ую k-перестановку заданного множества или –1, если такой нет.

Примеры

№	Входные данные	Выходные данные
1	4 1 2 6 8 3 9	3 9 6 8
2	4 4 2 6 8 3 9	9 3 6 8
3	4 5 2 6 8 3 9	-1

Как-то раз гному Кварку попала в руки карта сокровищ. На карте отмечено N точек, в которых может находиться клад. Все точки пронумерованы числами от 1 до N. Для каждой пары точек Кварк знает длину дороги, их соединяющей. Свои поиски Кварк начинает от точки с номером 1. Прежде чем начать свой долгий путь, хитрый гном вычеркивает точки, в которых, по его мнению, клада быть не может. Гарантируется, что точка с номером 1 никогда не бывает вычеркнута. После этого Кварк выбирает некоторый маршрут, проходящий через все оставшиеся на карте точки. Маршрут не проходит через одну и ту же точку более одного раза. Кварк может ходить только по дорогам, соединяющим невычеркнутые точки.

Кварк хочет выбрать маршрут минимальной длины. Необходимо найти такой маршрут для Кварка.

Входные данные
В первой строке находится одно целое число N (1 ≤ N ≤ 15) — количество точек, отмеченных на карте. В последующих N строках находятся расстояния между точками. В (i+1)-й строке находятся N целых чисел d_i1,d_i2, d_iN — длины дорог от i-й точки до всех остальных. Гарантируется, что d_ij=d_ji, d_ii=0 и 0 <d_ij <100. В (N+2)-й строке находится одно целое число Q (1 < Q ≤ 1000) — количество вариантов вычеркивания точек для данной карты. В последующих Q строках содержится описание вариантов вычеркивания. Описание начинается с числа C (0 ≤ C < N) — количества точек, в которых, по мнению Кварка, клада быть не может. Следующие C чисел задают номера этих точек.

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

Примеры

№	Входные данные	Выходные данные
1	3 0  45 10 45 0  30 10 30 0 2 0 1 3	40 45
2	5 0  14 20 17 14 14 0  15 19 18 20 15 0  15 16 17 19 15 0  14 14 18 16 14 0 2 3 5 4 3 0	14 58

Есть 4 квадрата, нарисованных горизонтально в ряд.

Вам дана строка S длиной 4, состоящие из 0 и 1.
Если i-й символ S равен 1, в i-м квадрате слева есть человек;
если i-й символ S равен 0, в i-м квадрате слева нет человека.

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

Выведите результат в виде строки в том же формате, что и S. (Для наглядности см. пример ввода / вывода).

Входные данные
На вход подается строка S длиной 4, состоящие из 0 и 1.

Выходные данные
Выведите строку длиной 4. i-й символ должен быть равен 1, если в i-м квадрате слева после перемещения будет человек, и 0 в противном случае.
 

Примеры

№	Входные данные	Выходные данные
1	1011	0101
2	1111	0111