Задача 4. Секретный секрет ≡

Условие

У Артема есть очень важный секрет. А так как Артем ещё и программист, то компьютерам свою тайну он не доверяет и хранит её в сейфе с особым замком.

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

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

Именно вам Артем до этого проговорился про устройство своего сейфа. Поэтому вы знаете, что для его открытия нужно объединить K ключей и порядке в котором это нужно сделать.

Попробуйте “чисто теоретически” понять, возможно ли этими ключами открыть сейф. И если это возможно, то как нужно скомбинировать эти ключи.

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

На вход программе в первой строке подаются два целых числа N, K.

Во-второй идут K целых чисел - формы ключей, которые нужно сложить, чтобы открыть сейф.

В следующих N строках перечисляются ключи, каждая строка - 4 целых числа - 4 формы, которые может принять ключ. F₀, ..., F₃

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

Выходной файл должен содержать последовательность из K различных целых чисел от 1 до N задающих номера ключей для каждого составляющего секретного ключа.

Если решения нет, выходной файл должен содержать единственное число -1.

Ограничения

1 ≤ N, K ≤ 12

0 ≤ F_i ≤ 128

Примеры тестов

5 4
84 69 83 84
65 66 67 68
84 84 84 84
83 84 83 84
67 82 69 84
69 79 82 83

4 5 3 2

9 7
66 97 100 101 114 105 107
72 101 108 108 111
32 116 111 32
97 108 108 32
109 121 32 32
102 97 110 115
32 97 110 100
32 116 111 32
100 117 99 107
102 117 110 115

-1

Разбор

Эта задача лишь аналог задачи «Слово из кубиков» Кленин А.А.

Идея - Полный перебор

На месте каждой составляющей секретного ключа может стоять любой из N ключей.

В худшем случае полный перебор займет N! = 12!.

Перебрать все варианты можно рекурсивным алгоритмом.

На каждый шаг рекурсии мы передаем массив bool used - какие ключи мы уже использовали и i сколько ключей мы уже подобрали.

Если i =  = K печатаем ключи и завершаем работу.