Сортування злиттям є одним з класичних алгоритмів сортування. Він ділить вхідний масив на дві частини, рекурсивно сортує кожну з них окремо та потім зливає дві відсортовані частини разом.
У цьому завданні алгоритм сортування злиттям сортує масив цілих чисел у зростаючому порядку. Точний опис алгоритму наведемо на псевдокоді:
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
Дуже важлива перестановка чисел від 1 до n була загублена через псування жорсткого диска. На щастя, послідовність сортувалася вище наведеним алгоритмом, а відладочна інформація з одиниць (1) і двійок (2) була записана на інший диск. За довжиною вхідної послідовності n та відладочною інформацією слід відновити вихідну послідовність цілих чисел.
Перший рядок містить кількість тестів t. Кожний тест складається з двох рядків. Перший рядок тесту містить довжину вихідної послідовності n (2 ≤ n ≤ 10000). Другий рядок містить послідовність символів 1 та 2 - відладочну інформацію програми сортування злиттям вихідної послідовності. Рядки розділяються символом "\n".
Щоб не виводити всю послідовність, слід обчислити та надрукувати лише її контрольну суму, яка обчислюється за наступним алгоритмом:
function checksum(arr): result = 1 for i=0 to arr.length()-1: result = (31 * result + arr[i]) mod 1000003 return result
Приклади
У першому прикладі n дорівнює 2, відладочна послідовність 1. Вихідною була послідовність 1 2 або 2 1. Відладочна інформація повідомляє нам, що перше число послідовності було менше за друге, тому вихідною послідовністю буде 1 2. Її контрольна сума дорівнює 994.
У другому прикладі n дорівнює 2, відладочна послідовність 2. На цей раз вихідною буде послідовність 2 1.
У третьому прикладі n дорівнює 4, відладочна послідовність 12212. Вихідна послідовність дорівнює 2 4 3 1.