Сортування злиттям є одним з класичних алгоритмів сортування. Він ділить вхідний масив на дві частини, рекурсивно сортує кожну з них окремо та потім зливає дві відсортовані частини разом. У цьому завданні алгоритм сортування злиттям сортує масив цілих чисел у зростаючому порядку. Точний опис алгоритму наведемо на псевдокоді: 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}.