Сортировка слиянием является одним из классических алгоритмов сортировки. Он делит входной массив на две части, рекурсивно сортирует каждую из них отдельно и затем сливает две отсотированные части вместе. В этой задаче алгоритм сортировки слиянием сортирует массив целых чисел в возрастающем порядке. Точное описание алгоритма приведем на псевдокоде: function merge_sort(arr): n = arr.length() if n <= 1: return arr // arr is indexed 0 through n-1, inclusive mid = floor(n/2) first_half = merge_sort(arr\[0..mid-1\]) second_half = merge_sort(arr\[mid..n-1\]) return merge(first_half, second_half) function merge(arr1, arr2): result = \[\] while arr1.length() > 0 and arr2.length() > 0: if arr1\[0\] < arr2\[0\]: print '1' // for debugging result.append(arr1\[0\]) arr1.remove_first() else: print '2' // for debugging result.append(arr2\[0\]) arr2.remove_first() result.append(arr1) result.append(arr2) return result Очень важная перестановка чисел от \textbf{1} до \textbf{n} была утеряна из-за порчи жесткого диска. К счастью, последовательность сортировалась выше приведенным алгоритмом и отладочная информация из единиц (\textbf{1}) и двоек (\textbf{2}) была записана на другой диск. По длине входной последовательности \textbf{n} и отладочной информации следует восстановить исходную последовательность целых чисел. \InputFile Первая строка содержит количество тестов \textbf{t}. Каждый тест состоит из двух строк. Первая строка теста содержит длину исходной последовательности \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{10000}). Вторая строка содержит последовательность символов \textbf{1} и \textbf{2} - отладочную информацию программы сортировки слияниям исходной последовательности. Строки разделяются символом "\textbf{\textbackslash n}". \OutputFile Чтобы не выводить всю последовательность, следует вычислить и напечатать только ее контрольную сумму, которая вычисляется по следующему алгоритму: function checksum(arr): result = 1 for i=0 to arr.length()-1: result = (31 * result + arr\[i\]) mod 1000003 return result \textbf{Примеры} В первом примере \textbf{n} равно \textbf{2}, отладочная последовательность \textbf{1}. Исходной была последовательность \textbf{1} \textbf{2} или \textbf{2} \textbf{1}. Отладочная информация сообщает нам, что первое число последовательности было меньше второго, поэтому исходной последовательностью будет \textbf{1} \textbf{2}. Ее контрольная сумма равна \textbf{994}. Во втором примере \textbf{n} равно \textbf{2}, отладочная последовательность \textbf{2}. На этот раз исходной будет последовательность \textbf{2 1}. В третьем примере \textbf{n} равно \textbf{4}, отладочная последовательность \textbf{12212}. Исходная последовательность равна \textbf{2} \textbf{4} \textbf{3} \textbf{1}.