У земного космического агентства есть традиция: каждое утро для экипажа космического корабля, находящегося на орбите, с Земли по спутниковой связи транслируют один или несколько музыкальных фрагментов. Однако, в последнее время астронавты стали жаловаться, что транслируемая музыка плохо сочетается с космосом. Поэтому агенство решило нанять популярную в Галактической Федерации рок-группу Abuse специально для сочинения космической музыки.
Музыканты долго трудились и выпустили композицию «Гипермузыка». Но, как часто бывает, заказчик остался недоволен результатом. Музыкальные эксперты космического агенства обнаружили, что в нотной записи композиции совершенно отсутствуют паузы, а сумма длительностей нот в такте не везде равна размеру такта. Музыканты объяснили это тем, что такова задумка, так как космос у них ассоциируется с беспрерывностью и бесконечностью. Но заказчик всегда прав, поэтому необходимо помочь группе добавить в такты минимальное количество пауз так, чтобы сумма длительностей нот и пауз в каждом такте была равна размеру такта.
Размеры всех тактов композиции одинаковы и задаются в условных единицах в виде обыкновенной дроби A / B. Длительности пауз и нот задаются в тех же условных единицах в виде обыкновенной дроби 1 / X. При этом знаменатели в размере такта и длительностях нот и пауз являются степенями двойки.
В первой строке задан размер такта в формате A / B, где 1 ≤ A, B ≤ 1024. Во второй строке задано количество тактов T (1 ≤ T ≤ 100). В каждой из следующих T строк задано описание одного такта.
В начале описания такта номер i задано количество нот в этом такте Ni (1 ≤ Ni, ), далее через пробел заданы длительности нот, каждая из которых соответствует формату 1 / X (1 ≤ X ≤ 1024).
Гарантируется, что:
Выведите T строк, по одной для каждого такта. Строка номер i должна содержать количество добавляемых пауз в такт номер i и их длительности. Паузы должны соответствовать формату 1 / Y, где Y — натуральное число, которое является целой степенью двойки.
Количество пауз должно быть минимально возможным, а длительности необходимо выводить в порядке убывания. Сумма длительностей нот и пауз в каждом такте в итоге должна быть равна размеру такта.
## Входные Данные
В первой строке задан размер такта в формате A / B, где 1 ≤ A, B ≤ 1024. Во второй строке задано количество тактов T (1 ≤ T ≤ 100). В каждой из следующих T строк задано описание одного такта.В начале описания такта номер i задано количество нот в этом такте Ni (1 ≤ Ni, ), далее через пробел заданы длительности нот, каждая из которых соответствует формату 1 / X (1 ≤ X ≤ 1024).Гарантируется, что: сумма длительностей нот в каждом такте не превышает его размера; все числители и знаменатели во вводе являются натуральными числами; все знаменатели являются целыми степенями двойки.
## Выходные Данные
Выведите T строк, по одной для каждого такта. Строка номер i должна содержать количество добавляемых пауз в такт номер i и их длительности. Паузы должны соответствовать формату 1 / Y, где Y — натуральное число, которое является целой степенью двойки.Количество пауз должно быть минимально возможным, а длительности необходимо выводить в порядке убывания. Сумма длительностей нот и пауз в каждом такте в итоге должна быть равна размеру такта.
## Примеры
Входные данные4/442 1/8 1/81 1/11 1/162 1/4 1/2Выходные данные2 1/2 1/404 1/2 1/4 1/8 1/161 1/4Входные данные3/421 1/42 1/8 1/16Выходные данные1 1/22 1/2 1/16Входные данные24/1622 1/8 1/12 1/8 1/4Выходные данные2 1/4 1/82 1/1 1/8
[samples]
**Definitions**
Let $ \frac{A}{B} \in \mathbb{Q} $ be the time signature (measure length), where $ A, B \in \mathbb{Z}^+ $ and $ B = 2^p $ for some $ p \in \mathbb{N} $.
Let $ T \in \mathbb{Z}^+ $ be the number of measures.
For each measure $ i \in \{1, \dots, T\} $:
- Let $ N_i \in \mathbb{Z}^+ $ be the number of notes.
- Let $ D_i = \left\{ \frac{1}{x_{i,j}} \mid j \in \{1, \dots, N_i\},\ x_{i,j} = 2^{k_{i,j}},\ k_{i,j} \in \mathbb{N} \right\} $ be the set of note durations.
**Constraints**
1. $ 1 \leq A, B \leq 1024 $, $ B $ is a power of two.
2. $ 1 \leq T \leq 100 $.
3. For each measure $ i $: $ 1 \leq N_i $, each note duration $ \frac{1}{x_{i,j}} $ has $ x_{i,j} $ a power of two, $ 1 \leq x_{i,j} \leq 1024 $.
4. The total duration of notes in each measure is strictly less than $ \frac{A}{B} $.
**Objective**
For each measure $ i $, find the minimal number of rests such that:
$$
\sum_{j=1}^{N_i} \frac{1}{x_{i,j}} + \sum_{k=1}^{R_i} \frac{1}{y_{i,k}} = \frac{A}{B}
$$
where each $ y_{i,k} $ is a power of two, and $ R_i $ is minimized.
Output $ R_i $ and the rest durations $ \frac{1}{y_{i,1}}, \frac{1}{y_{i,2}}, \dots, \frac{1}{y_{i,R_i}} $ in **non-increasing order**.