Лаврушка və massivlərin parçalanması

Лavruşka — vicdanlı bir şagirdir və proqramçı olmaq istəyir. Son informatika dərsində onun sevimli müəllimi ona belə bir tapşırıq verdi. Tutaq ki, a[1], ..., a[N] — müəyyən bir təbii ədədlər ardıcıllığıdır. Lavruşka 1, 2, 3, ..., N ədədlər ardıcıllığını iki ardıcıllığa b[1], ..., b[M] və c[1], ..., c[K] bölməlidir ki:

• Hər bir təbii ədəd 1 ≤ r ≤ N dəqiq bir dəfə b və ya c ardıcıllığının elementi olsun (yəni M + K = N).

• Hər bir indeks cütü üçün 1 ≤ i, j ≤ M, i ≠ j, a[bi] və a[bj] ədədləri qarşılıqlı sadə olsun.

• Hər bir indeks cütü üçün 1 ≤ i, j ≤ K, i ≠ j, a[ci] və a[cj] ədədləri qarşılıqlı sadə olsun.

Ən böyük ortaq böləni bir olan ədədlər qarşılıqlı sadə adlanır. 1, 2, 3, ..., N ardıcıllığının uyğun bölünməsini a[i] ardıcıllığının parçalanması adlandıracağıq.

Ardıcıllığın parçalanması qeyri-müəyyən ola bilər. Buna görə də müəllim Lavruşkadan b[i] ardıcıllığındakı elementlərin sayını maksimumlaşdıran belə bir parçalanma tapmasını istədi. Əgər b[i] ardıcıllığındakı elementlərin sayını maksimumlaşdıran bir neçə parçalanma varsa, onda b[i] ardıcıllığının leksikoqrafik olaraq ən kiçik olduğu parçalanmanı tapmaq lazımdır.

q[1], q[2], ..., q[W] ardıcıllığının p[1], p[2],..., p[W] ardıcıllığından leksikoqrafik olaraq kiçik olduğunu deyəcəyik, əgər elə bir i varsa ki, q[i]˂p[i], və istənilən j˂i üçün p[j] = q[j] şərti ödənilir.

Tapşırıq

Verilmiş a ardıcıllığı üçün 1, 2, 3, …, N ədədlər ardıcıllığını iki ardıcıllığa b[1], ..., b[M] və c[1], ..., c[K] optimal şəkildə bölən proqram yazın.

Giriş məlumatları

Giriş məlumatlarının birinci sətirində Z (1 ≤ Z ≤ 3) — test giriş məlumatlarının sayı (müəllim Lavruşkaya bu tapşırığı müxtəlif giriş məlumatları üçün bir neçə dəfə təklif etdi).

Sonra Z test məlumatları aşağıdakı formatda verilir.

Məlumatların birinci sətirində N (1 ≤ N ≤ 100000) — a ardıcıllığının elementlərinin sayı verilir. Növbəti sətirdə boşluqla ayrılmış N ədəd — a ardıcıllığının elementləri (1 ≤ ai ≤ 2000000) verilir.

Çıxış məlumatları

Hər bir test məlumatı üçün çıxış faylında bir sətirdə M — b ardıcıllığının elementlərinin sayı, ikinci sətirdə isə a ardıcıllığının b ardıcıllığına daxil olan elementlərinin artan sıra nömrələri ilə M təbii ədəd verin.

Əgər belə bir vəziyyət yaranarsa ki, müəllim səhv edib və a ardıcıllığının heç bir parçalanması mövcud deyilsə, bir sətirdə -1 çıxarın.

Qiymətləndirmə

Test dəsti 4 blokdan ibarətdir və hər biri üçün aşağıdakı şərtlər yerinə yetirilir:

1. 24 % xal: N ≤ 15, 1 ≤ a[i] ≤ 2000000.

2. 24 % xal: N ≤ 1000, 1 ≤ a[i] ≤ 2000000.

3. 30 % xal: N ≤ 20000, 1 ≤ a[i] ≤ 2000000.

4. 22 % xal: N ≤ 100000, 1 ≤ a[i] ≤ 2000000.

İzah. Birinci test məlumatları dəstində b ardıcıllığında 1, 2, ..., N bütün elementlərini ehtiva edən bir parçalanma əldə etmək mümkün deyil, çünki 2 və 4 ədədləri qarşılıqlı sadə deyil. İkinci test məlumatları dəstində isə ümumiyyətlə a ardıcıllığının heç bir parçalanması mövcud deyil.