{"raw_statement":[{"iden":"statement","content":"У земного космического агентства есть традиция: каждое утро для экипажа космического корабля, находящегося на орбите, с Земли по спутниковой связи транслируют один или несколько музыкальных фрагментов. Однако, в последнее время астронавты стали жаловаться, что транслируемая музыка плохо сочетается с космосом. Поэтому агенство решило нанять популярную в Галактической Федерации рок-группу Abuse специально для сочинения космической музыки.\n\nМузыканты долго трудились и выпустили композицию «Гипермузыка». Но, как часто бывает, заказчик остался недоволен результатом. Музыкальные эксперты космического агенства обнаружили, что в нотной записи композиции совершенно отсутствуют паузы, а сумма длительностей нот в такте не везде равна размеру такта. Музыканты объяснили это тем, что такова задумка, так как космос у них ассоциируется с беспрерывностью и бесконечностью. Но заказчик всегда прав, поэтому необходимо помочь группе добавить в такты минимальное количество пауз так, чтобы сумма длительностей нот и пауз в каждом такте была равна размеру такта.\n\nРазмеры всех тактов композиции одинаковы и задаются в условных единицах в виде обыкновенной дроби A / B. Длительности пауз и нот задаются в тех же условных единицах в виде обыкновенной дроби 1 / X. При этом знаменатели в размере такта и длительностях нот и пауз являются степенями двойки.\n\nВ первой строке задан размер такта в формате A / B, где 1 ≤ A, B ≤ 1024. Во второй строке задано количество тактов T (1 ≤ T ≤ 100). В каждой из следующих T строк задано описание одного такта.\n\nВ начале описания такта номер i задано количество нот в этом такте Ni (1 ≤ Ni, ), далее через пробел заданы длительности нот, каждая из которых соответствует формату 1 / X (1 ≤ X ≤ 1024).\n\nГарантируется, что: \n\nВыведите T строк, по одной для каждого такта. Строка номер i должна содержать количество добавляемых пауз в такт номер i и их длительности. Паузы должны соответствовать формату 1 / Y, где Y — натуральное число, которое является целой степенью двойки.\n\nКоличество пауз должно быть минимально возможным, а длительности необходимо выводить в порядке убывания. Сумма длительностей нот и пауз в каждом такте в итоге должна быть равна размеру такта.\n\n"},{"iden":"входные данные","content":"В первой строке задан размер такта в формате A / B, где 1 ≤ A, B ≤ 1024. Во второй строке задано количество тактов T (1 ≤ T ≤ 100). В каждой из следующих T строк задано описание одного такта.В начале описания такта номер i задано количество нот в этом такте Ni (1 ≤ Ni, ), далее через пробел заданы длительности нот, каждая из которых соответствует формату 1 / X (1 ≤ X ≤ 1024).Гарантируется, что:   сумма длительностей нот в каждом такте не превышает его размера;  все числители и знаменатели во вводе являются натуральными числами;  все знаменатели являются целыми степенями двойки. "},{"iden":"выходные данные","content":"Выведите T строк, по одной для каждого такта. Строка номер i должна содержать количество добавляемых пауз в такт номер i и их длительности. Паузы должны соответствовать формату 1 / Y, где Y — натуральное число, которое является целой степенью двойки.Количество пауз должно быть минимально возможным, а длительности необходимо выводить в порядке убывания. Сумма длительностей нот и пауз в каждом такте в итоге должна быть равна размеру такта."},{"iden":"примеры","content":"Входные данные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"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ \\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} $.  \nLet $ T \\in \\mathbb{Z}^+ $ be the number of measures.  \nFor each measure $ i \\in \\{1, \\dots, T\\} $:  \n- Let $ N_i \\in \\mathbb{Z}^+ $ be the number of notes.  \n- 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.  \n\n**Constraints**  \n1. $ 1 \\leq A, B \\leq 1024 $, $ B $ is a power of two.  \n2. $ 1 \\leq T \\leq 100 $.  \n3. 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 $.  \n4. The total duration of notes in each measure is strictly less than $ \\frac{A}{B} $.  \n\n**Objective**  \nFor each measure $ i $, find the minimal number of rests such that:  \n$$\n\\sum_{j=1}^{N_i} \\frac{1}{x_{i,j}} + \\sum_{k=1}^{R_i} \\frac{1}{y_{i,k}} = \\frac{A}{B}\n$$  \nwhere each $ y_{i,k} $ is a power of two, and $ R_i $ is minimized.  \nOutput $ 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**.","simple_statement":"Given a time signature A/B and T measures, for each measure, you’re given a list of note durations (each is 1/X). Add the minimum number of rests (each rest is 1/Y, where Y is a power of 2) so that the total duration of notes and rests in each measure equals A/B. Output the number of rests and their durations in descending order.","has_page_source":false}