Поновлення послідовності#2822

Поновлення послідовності

1 секунда

64 мегабайти

Легка

Сортування злиттям (merge sort) — це один із класичних алгоритмів сортування. Він ділить вхідний масив навпіл, рекурсивно сортує кожну половину, а потім зливає дві відсортовані половини.

У цій задачі алгоритм сортування злиттям упорядковує масив цілих чисел за зростанням. Точна поведінка описана наступним псевдокодом:

function merge_sort(arr):
    n = arr.length()
    if n <= 1:
        return arr
    // arr індексується від 0 до n-1 включно
    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' // для відлагодження
            result.append(arr1[0])
            arr1.remove_first()
        else:
            print '2' // для відлагодження
            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$ .

Приклад 1