Формат входных данных. Формат выходных данных. Примеры

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

В первой строке входного файла задается 5 целых чисел: N, M, K, T и Z (1 ≤ N, M ≤ 10, 0 ≤ K, T ≤ 20, 1 ≤ Z ≤ 100000). В каждой из следующих K строк расположены координаты соответствующей клетки с ловушкой X, Y (0 ≤ X ≤ N, 0 ≤ Y ≤ M). Гарантируется, что все клетки с ловушками различные и в клетках (0, 0) и (N, M) ловушек нет.

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

Выведите требуемое число.

Примеры

turtle. in	turtle. out
1 1 1 0 1000 0 1
2 2 0 0 10

D. Фродо и монстр

Фродо борется с монстром, головы которого последовательно пронумерованы от 1 до K. Монстр — носитель кибернетического генома, и он характеризуется весьма необычными свойствами. Если Фродо отрежет голову с нечётным номером X, тогда у монстра на этом месте вырастет Y голов, где Y — максимальное простое число, меньшее X. При отрезании первой головы новая голова не вырастает. Известно, что на шее монстра не вмещается более 30 000 000 голов (то есть, если сумма Y и оставшихся голов больше 30000000, тогда количество голов будет в точности 30 000 000).

Если Фродо отрежет голову с чётным номером Z, тогда у монстра отваливаются все те головы, номера которых в двоичной системе содержат столько единиц, сколько содержит Z. Если монстр лишается всех голов, то бой прекращается.

По результатам каждого удара Фродо (как после вырастания новых голов, так и после того, как некоторые головы отвалились) головы монстра перенумеровываются заново, начиная с 1.

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

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

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

В первой строке входного файла находятся два разделённых пробелом целых числа K (2 ≤ K ≤ 30000000) и N (2 ≤ N ≤ 200 000), где K — начальное количество голов монстра, а N — количество отрезаний. В каждой из следующих N строк записано целое число. Эти числа описывают последовательность номеров отрезанных голов. Номера голов корректны, то есть они никогда не превышают общее количество голов монстра в момент удара.

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

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

Пример

monster. in	monster. out
7 4

Пояснение к примеру

После отрезания головы номер 5 у монстра вырастут ещё 3 головы и их станет 9. После отрезания девятой головы у монстра вырастут ещё 7 голов и их станет 15. После отрезания шестой головы у монстра отвалятся головы с номерами 3, 5, 9, 10 и 12, а после отрезания головы номер 4 — головы 8, 2 и 1. В итоге у монстра останется 5 голов.