Hd0105. Количество чисел в наборе 2

Дано два массива целых чисел, первый длины n, второй длины m. Найти количество чисел из второго массива, содержащихся в первом.

Формат входных данных  В первой строке вводятся два числа n и m (0<=n,m<=10⁵). Во второй строке через пробел записаны n чисел из первого массива, в третьей строке записано m чисел из второго массива. Числа массивов не превосходят 10⁹ по абсолютной величине.

Формат выходных данных  Выведите одно число - ответ к задаче.

Пример

Ввод	Вывод
2 3 2 3 1 3 3	2

Hd0106. Сортировка 2

Дан массив целых чисел длины n. Необходимо отсортировать его и вывести.

Формат входных данных  В первой строке вводится число n (1<=n<=10⁵). Во второй строке через пробел записаны n целых 4-х битных знаковых чисел.

Формат выходных данных  Выведите в одну строчку n чисел отсортированного массива через пробел.

Пример

Ввод	Вывод
5 5 3 2 1 5	1 2 3 5 5

HD0107. Резать колбасу!

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

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

Формат входных данных

Первая строка входного файла содержит два целых числа n и m (1 ≤ n, m ≤ 100) — соответственно, высоту и ширину листа бумаги в клетках. Вторая строка входного файла содержит число k (1 ≤ k ≤ 1000).

Формат выходных данных

Если данный листок бумаги нельзя разрезать указанным образом, в выходной файл выведите «-1».

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

Ввод	Вывод
2 2 1	1 2 3 4
2 2 2	1 1 2 2
2 2 3	-1
4 4 4	1 1 1 4 1 4 4 4 2 2 3 3 2 2 3 3

Hd0108. Карточный фокус

Джим работает престидижитатором. Иначе говоря, он фокусник. Основная специализация Джима — карточные фокусы.

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

И тут начинается магическое действие. Джим берет перемешанную колоду карт так, чтобы карты находились рубашкой вверх. Затем он раскладывает карты из колоды по m кучкам, причем верхняя карта колоды попадает в первую кучку, вторая сверху — во вторую, m+ 1-ая карта, если такая есть в колоде, попадает снова в первую кучку, m + 2-ая во вторую и т.д. После этого Джим спрашивает зрителя, в какой из кучек находится загаданная зрителем карта. Пусть карта попала в i-ую кучку. После этого Джим собирает кучки карт обратно в одну колоду. При этом i-ая кучка оказывается сверху новой колоды, под ней i + 1-ая и так до n-ой, после которой следует первая кучка и так до i - 1-ой. При этом порядок карт в каждой кучке сохраняется, то есть первая карта, положенная в кучку оказывается верхней в кучке, вторая — под ней. Повторяя данные операции несколько раз, через некоторое время Джим говорит, что путем магии и волшебства добился того, чтобы загаданная карта оказалась верхней в колоде. И карта действительно оказывается верхней.

Рассмотрим пример такого фокуса. Пусть n = 6 и карты обозначаются числами от 1 до 6, а m = 2. Пусть зритель загадал карту 1, а помешанная колода имеет вид (4, 2, 1, 5, 6, 3). При первом раскладывании по кучкам получаются кучки (4, 1, 6) и (2, 5, 3), после чего Джим собирает из этих кучек колоду (4, 1, 6, 2, 5, 3). На следующем шаге кучки (4, 6, 5) и (1, 2, 3), после этого колода имеет вид (1, 2, 3, 4, 6, 5). И с помощью магии загаданная карта оказалась верхней!

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

Напишите программу, которая по данным n и m найдет минимальное k