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

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

Петрик и Василько — настоящие друзья, поэтому они постоянно задают друг другу всевозможные интересные задачи. Однако Василько всегда с легкостью решает задачи своего друга, поэтому Петрик решил придумать по-настоящему сложную задачу. И вот что у него получилось. Будем называть число b подчислом числа a , если из числа a можно вычеркнуть некоторые цифры так, что цифры, которые остались, образуют число b . Задано n -цифровое число x . Обозначим как x _k наибольшее k -цифровое подчисло числа x . Необходимо ответить на m запросов. Каждый запрос состоит из двух цифр - k и l . Ответом на запрос является l -я цифра числа x _k . На этот раз задача действительно заставила Василько задуматься. А сможете ли вы решить ее быстрее его?

В стране Олимпия сегодня праздник! Единственное почтовое отделение на улице Олимпийская переполнено подарками, которые необходимо как можно быстрее доставить их адресатам. Всего в этот день поступило n подарков, i -й из которых необходимо доставить в дом с номером h _i . Несколько различных подарков могут быть адресованы в один дом. Почтовое отделение расположено в начале Олимпийской улицы. Справа от почты вдоль прямой дороги находятся дома, нумерация которых начинается с 1 ; i -й дом расположен в i километрах от почты. Для доставки предметов в экспериментальном режиме используется единый специальный почтовый робот, который одновременно вмещает не более k предметов. Загрузка и разгрузка одного подарка длится одну минуту, робот не может загружать и разгружать одновременно. Один километр робот преодолевает тоже за одну минуту.

Напишите программу, которая по информации о каждом из подарков и характеристике робота определяет наименьшее время в минутах, за которое робот сможет доставить все подарки их адресатам и вернуться в почтовое отделение. Сначала все подарки и робот находятся в отделении.

Мэр столицы Котоляндии, наконец, согласился построить в городе метро. Теперь его ожидает чрезвычайно важная задача — сэкономить как можно больше денег на его постройке.

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

Пассажиры должны будут заплатить некоторое количество денег для того, чтобы войти в метро на определенной станции. При этом для разных станций эта сумма может быть разной. А именно: для некоторой станции x стоимость входа (в гривнах) будет равна максимальному количеству тоннелей, которые пассажир должен проехать для того, чтобы доехать от станции x к любой другой станции y .

Кроме того, мэр города очень придирчив к числам. Известно, что мэр любит числа a ₁ , ..., a _n , а также ненавидит числа b ₁ , ..., b _m . Мэр не согласится на постройку метро, если в стоимости прохода в метро хотя бы на одной из станций будет хотя бы одно число, которое он ненавидит, а также если не будет ни одной станции с стоимостью прохода, равной какому-то числу, которое он любит.

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

Лавруша~--- добросовестный ученик, который мечтает стать программистом. На последнем уроке информатики его любимая учительница предложила ему решить такую задачу.

Лавруше дана последовательность натуральных чисел \(a_1,\ldots, a_n\). Ему нужно разделить последовательность чисел \(1,2,3, \ldots, n\) на две последовательности \(b_1, \ldots, b_m\) и \(c_1, \ldots, c_k\) таким образом, чтобы:

1. Каждое натуральное число \(1 \le r \le n\) было элементом ровно одной из последовательностей \(b\) или \(c\).

2. Для каждой пары индексов \(1 \le i, j \le m, i \ne j\) числа \(a_{b_i}\) и \(a_{b_j}\) были взаимно простыми. Взаимно простыми называются числа, наибольший общий делитель которых равен единице.

3. Для каждой пары индексов \(1 \le i, j \le k, i \ne j\) числа \(a_{c_i}\) и \(a_{c_j}\) были взаимно простыми.

Разбиение последовательности может быть неоднозначно. Поэтому учительница попросила Лаврушу найти такое разбиение, чтобы оно максимизировало количество элементов в последовательности \(b_i\). Если существует несколько разбиений, которые максимизируют количество элементов в последовательности \(b_i\), то нужно найти среди них такое, чтобы последовательность \(b_i\) была лексикографически наименьшей.

Будем говорить, что последовательность \(q_1, q_2, \ldots, q_W\) является лексикографически меньше последовательности \(p_1, p_2, \ldots, p_W\), если существует такое \(i\), что \(q_i < p_i\), а для произвольного \(j < i\) выполняется \(p_j = q_j\).

Напишите программу, которая для заданной последовательности чисел \(a\) найдет оптимальное разбиение последовательности цифр \(1,2,3, \ldots, n\) на две последовательности \(b_1, \ldots, b_m\) и \(c_1, \ldots, c_k\).