Помехи

При передаче информационных сообщений по каналам связи часто возникают ошибки, и получается что полученное сообщение отличается от отправленного. Для борьбы с этим применяют различные коды обнаружения ошибок, а также корректирующие коды, позволяющие исправлять наиболее вероятные ошибки. Одним из методов обнаружения ошибок является передача вместе с сообщением некоторого хеша — контрольной суммы, которую можно рассчитать для полученного сообщения и сравнить с контрольной суммой исходного сообщения.

В этой задаче вам необходимо будет реализовать коррекцию ошибок в полученном сообщении с помощью контрольной суммы, которая рассчитывается как полиномиальный хеш. Будем считать, что передается некоторая битовая строка, хранящаяся как двоичное число из n бит. Если пронумеровать биты числа с нуля, начиная с младшего, то полиномиальный хеш рассчитывается по следующей формуле:

h(a) = (a0 + a1t + a2t 2 + ... + a**i t* i* + ... + a**n − 1t** n − 1) mod M, где a**i — i -й бит числа.

В этой задаче всегда t = 239, M = 109 + 7.

Принимающая сторона получает, возможно искаженное, сообщение и полиномиальный хеш, рассчитанный для отправленного сообщения. Считается, что сам хеш передается без ошибок. Исправление ошибок происходит по методу наибольшего правдоподобия — необходимо найти сообщение, отличающееся от полученного в минимальном числе бит, и имеющее хеш, равный полученному.

Первая строка содержит единственное число K (1 ≤ K ≤ 10) — количество переданных сообщений. Каждая из следующих K строк содержит описание переданного сообщения — три целых числа n (1 ≤ n ≤ 34) — длина сообщения, m (0 ≤ m < 2n ) — число, двоичная запись которого задает битовую строку полученного сообщения и h (0 ≤ h < 109+7) — полученный хеш.

Суммарная длина всех переданных сообщений в одном тесте не превосходит 100.

Для каждого сообщения в отдельной строке необходимо вывести единственное число «−1», если это сообщение невозможно расшифровать, иначе необходимо сначала вывести число d — минимальное количество ошибок и далее в этой же строке d чисел — номера битов, которые были искажены при передаче. Если возможных ответов несколько, выведите любой.