Задача №114670. Проверка
КэВэ — учитель математики в школе. У него есть любимая последовательность чисел \(b_1, b_2,\ \ldots,\ b_m\), состоящая из \(m\) различных чисел. Когда КэВэ скучно при проверке домашних заданий, он ищет \(b\) в виде подпоследовательности чисел, записанных в тетради ученика.
Как-то раз КэВэ увидел в тетради ученика последовательность из \(n\) чисел \(a_1, a_2,\ \ldots,\ a_n\). Учитель решил применить новый метод проверки домашних заданий. А именно, для каждой позиции \(i\) КэВэ ищет минимальный индекс \(r_i\), такой что в последовательности \(a_i,\ a_{i + 1},\ a_{i + 2},\ \ldots,\ a_{r_i}\) можно встретить \(b\) как подпоследовательность. Помогите ему для каждого \(i\) найти нужное \(r_i\) или укажите, что такого не найдётся.
Напомним, что подпоследовательностью для \(a_1, a_2,\ \ldots,\ a_n\) называется набор элементов \(a\), полученный из \(a_1, a_2,\ \ldots,\ a_n\) удалением некоторых ее элементов без изменения порядка следования оставшихся.
В первой строке вводится два целых числа \(n\) и \(m\) (\(1 \le n,\,m \le 200\,000\)) — длина последовательности \(a\) и \(b\) соответственно.
Во второй строке вводится \(n\) целых чисел \(a_1,\ a_2,\ a_3,\ \ldots,\ a_n\) (\(1 \le a_i \le 200\,000\)).
В третьей строке вводится \(m\) целых чисел \(b_1,\ b_2,\ b_3,\ \ldots,\ b_m\) (\(1 \le b_i \le 200\,000\)). Гарантируется, что все числа последовательности \(b_i\) различны.
В единственной строке выведите \(n\) чисел, \(i\)-е из них должно быть равно искомому индексу \(r_i\). В случае, если такого \(r_i\) не найдётся, выведите вместо него число \(-1\).
В первом примере \(b\) обязательно закончится в позиции 6, потому что это единственное число 2, стоящее после числа 3. Например, элементы с позиций \(\{3,\,4,\,6\}\) дают нужную подпоследовательность
Во втором примере подпоследовательность \(b\) встречается в элементах с позиций \(\{3,\,4\}\) и \(\{8,\,9\}\).
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | |||||
| Группа Баллы | \(n\) | \(m\) | Необх. группы | Комментарий | |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 10 | \(n \leq 50\) | \(m \le 50\) | 0 | |
| 2 | 11 | \(n \leq 1000\) | \(m \leq 1000\) | 0, 1 | |
| 3 | 12 | \(n \leq 10000\) | \(m \le 10000\) | 0, 1, 2 | |
| 4 | 22 | – | \(m \leq 2\) | ||
| 5 | 15 | – | \(m \leq 1000\) | 0, 1, 2, 4 | |
| 6 | 30 | – | – | 0, 1, 2, 3, 4, 5 | |
7 3 1 2 1 3 1 2 1 1 3 2
6 6 6 -1 -1 -1 -1
10 2 1 2 3 4 5 1 2 3 4 5 3 4
4 4 4 9 9 9 9 9 -1 -1