Проста задача#11817
Назвемо непорожню послідовність додатних цілих чисел дивною, якщо сума її елементів є простим числом.
Задано масив довжини , що складається з простих чисел. Також задано ціле число .
Розбийте масив на непорожніх підпослідовностей^1 так, щоб кожен елемент масиву належав рівно одній з них, а кількість дивних підпослідовностей серед утворених була мінімально можливою.
У цій задачі кожен тест містить кілька наборів вхідних даних. Вам потрібно розв'язати задачу незалежно для кожного такого набору.
Зауважте, що в цій задачі немає блоку «без додаткових обмежень».
У першому рядку задано одне ціле число (1\le T\le 10^5) — кількість наборів вхідних даних. Далі задано опис наборів вхідних даних.
У першому рядку кожного набору вхідних даних задано два цілі числа , (1 \le k \le n \le 10^5) — довжина масиву та кількість підпослідовностей, на які його потрібно розбити.
У другому рядку кожного набору вхідних даних задано простих чисел a_1, a_2, \ldots, a_n (2\le a_i\le 10^5, a_i\le a_{i+1}) — елементи масиву .
Гарантується, що сума по всім наборам вхідних даних одного тесту не перевищує 10^5.
Для кожного набору вхідних даних виведіть оптимальне розбиття у наступному форматі:
у першому рядку виведіть одне ціле число — кількість дивних підпослідовностей серед утворених;
у кожному з наступних рядків виведіть цілі числа s_i та b_1, b_2, \ldots, b_{s_i} (1\le s_i\le n) — кількість елементів у відповідній підпослідовності розбиття та самі її елементи.
Підпослідовності та їхні елементи дозволяється виводити в будь-якому порядку.
Якщо існує кілька правильних відповідей, дозволяється вивести будь-яку з них.
Приклад 1
^1 Послідовність називається підпослідовністю масиву , якщо можливо видалити певну кількість елементів з масиву (можливо, нульову) так, щоб утворилась послідовність .