Серия дорог
Дон и Джен часто путешествуют вместе и, чтобы не скучать в дороге, придумали несколько игр, связанных с номерными знаками и дорожными знаками. Одна из их любимых игр называется "Дорожный Рядок". В этой игре нужно последовательно находить числа: сначала 1, затем 2, потом 3 и так далее. Когда они доходят до двузначных чисел, обе цифры должны быть рядом друг с другом на знаке или номерном знаке. Один знак может содержать несколько подходящих чисел. Например, если они видят знак с символами "678-43 15", они могут использовать числа 67, 78, 43 и 15, но не 84 (из-за тире между цифрами) или 31 (из-за пробела между цифрами). Они также могут использовать отдельные цифры 6, 7, 8, 4, 3, 1 и 5, а также трехзначное число 678 (если они дошли до такого уровня).
Изначально в игре были строгие правила: нельзя было находить число n, пока не найдены все числа от 1 до n-1. Однако вскоре они поняли, что это делает игру слишком медленной, и изменили правила. Теперь они называют число n последним полным числом, если оно является наибольшим числом, для которого найдены все числа от 1 до n. (В начале игры 0 считается последним полным числом.)
С учетом этого, Дон и Джен решили отслеживать некоторые числа, которые они видели за пределами последнего полного числа n, при условии, что они не слишком велики. Точнее, они могут запоминать числа в окне размером w за пределами n. Это позволяет им запомнить любое число до n+w.
Например, если w = 4, и последнее полное число, которое они видели, это 19, то, увидев следующий знак:
"Show time at 8:25, no one under 21 admitted"
они могут использовать 21, но не 25 (так как оно не в окне). Если за этим знаком следует другой:
"The FleaBag Hotel, phone 555-2520"
они могут использовать 20, что делает 21 последним полным числом, и теперь они могут использовать 25, так как оно попадает в окно.
Входные данные
Первая строка входного файла содержит целое число m, обозначающее количество тестовых случаев. Каждый тестовый случай начинается с пары положительных целых чисел k w, где k ≤ 1000 — это количество знаков, увиденных Доном и Джен, а w ≤ 100 — размер окна. Далее следуют k строк, каждая из которых содержит текст с какого-либо знака. Каждая строка может содержать любую комбинацию буквенно-цифровых символов, знаков препинания и пробелов и будет длиной не более 1000. Ввод для каждого знака заканчивается новой строкой.
Выходные данные
Для каждого тестового случая выведите номер случая, затем последнее полное число, которое можно найти с помощью знаков, и наибольшее число, увиденное в пределах окна.