B. Медианы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a = [1, 2, \ldots, n]$$$, где $$$n$$$ — нечетное, и целое число $$$k$$$.

Ваша задача — выбрать нечетное положительное целое число $$$m$$$ и разбить массив $$$a$$$ на $$$m$$$ подмассивов$$$^{\dagger}$$$ $$$b_1, b_2, \ldots, b_m$$$ так, чтобы:

  • Каждый элемент массива $$$a$$$ принадлежит ровно одному подмассиву.
  • Для всех $$$1 \le i \le m$$$, $$$|b_i|$$$ — нечетное, т.е. длина каждого подмассива нечетная.
  • $$$\operatorname{median}([\operatorname{median}(b_1), \operatorname{median}(b_2), \ldots, \operatorname{median}(b_m)]) = k$$$, т.е. медиана$$$^{\ddagger}$$$ массива медиан всех подмассивов должна равняться $$$k$$$. $$$\operatorname{median}(c)$$$ обозначает медиану массива $$$c$$$.

$$$^{\dagger}$$$Подмассив массива $$$a$$$ длины $$$n$$$ — это массив $$$[a_l, a_{l + 1}, \ldots, a_r]$$$ для некоторых целых чисел $$$1 \le l \le r \le n$$$.

$$$^{\ddagger}$$$Медиана массива нечетной длины — это средний элемент после сортировки массива в неубывающем порядке. Например: $$$\operatorname{median}([1,2,5,4,3]) = 3$$$, $$$\operatorname{median}([3,2,1]) = 2$$$, $$$\operatorname{median}([2,1,2,1,2,2,2]) = 2$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n < 2 \cdot 10^5$$$, $$$n$$$ — нечетное) — длина массива $$$a$$$ и требуемая медиана массива медиан всех подмассивов.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных:

  • Если подходящего разбиения нет, выведите $$$-1$$$ в одной строке.
  • В противном случае, в первой строке выведите нечетное целое число $$$m$$$ ($$$1 \le m \le n$$$) — количество подмассивов в разбиении, а во второй строке выведите $$$m$$$ различных целых чисел $$$p_1, p_2 , p_3 , \ldots, p_m$$$ ($$$1 = p_1 < p_2 < p_3 < \ldots < p_m \le n$$$) — обозначающие левые границы каждого подмассива.

А именно, для корректного ответа $$$[p_1, p_2, \ldots, p_m]$$$:

  • $$$b_1 = \left[ a_{p_1}, a_{p_1 + 1}, \ldots, a_{p_2 - 1} \right]$$$
  • $$$b_2 = \left[ a_{p_2}, a_{p_2 + 1}, \ldots, a_{p_3 - 1} \right]$$$
  • $$$\ldots$$$
  • $$$b_m = \left[ a_{p_m}, a_{p_m + 1}, \ldots, a_n \right]$$$.

Если существует несколько решений, вы можете вывести любое из них.

Пример
Входные данные
4
1 1
3 2
3 3
15 8
Выходные данные
1
1
3
1 2 3
-1
5
1 4 7 10 13
Примечание

В первом наборе входных данных при данном разбиении $$$m = 1$$$ и $$$b_1 = [1]$$$. Очевидно, что $$$\operatorname{median}([\operatorname{median}([1])]) = \operatorname{median}([1]) = 1$$$.

Во втором наборе входных данных при данном разбиении $$$m = 3$$$ и:

  • $$$b_1 = [1]$$$
  • $$$b_2 = [2]$$$
  • $$$b_3 = [3]$$$

Следовательно, $$$\operatorname{median}([\operatorname{median}([1]), \operatorname{median}([2]), \operatorname{median}([3])]) = \operatorname{median}([1, 2, 3]) = 2$$$.

В третьем наборе входных данных нет корректного разбиения для $$$k = 3$$$.

В четвертом наборе входных данных при данном разбиении $$$m = 5$$$ и:

  • $$$b_1 = [1, 2, 3]$$$
  • $$$b_2 = [4, 5, 6]$$$
  • $$$b_3 = [7, 8, 9]$$$
  • $$$b_4 = [10, 11, 12]$$$
  • $$$b_5 = [13, 14, 15]$$$

Следовательно, $$$\operatorname{median}([\operatorname{median}([1, 2, 3]), \operatorname{median}([4, 5, 6]), \operatorname{median}([7, 8, 9]), \operatorname{median}([10, 11, 12]), \operatorname{median}([13, 14, 15])]) = \operatorname{median}([2, 5, 8, 11, 14]) = 8$$$.