22154번 - Помехи 스페셜 저지다국어

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

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

h(a) = (a₀ + a₁t + a₂t ² + ... + a_i t ⁱ + ... + a_n − 1t ^n − 1) mod M, где a_i — i -й бит числа.

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

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

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

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

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