Suffikslərin çevrilməsi
Verilmiş mətn s[1..n] uzunluğunda n simvoldan ibarətdir. Bu mətnin bütün sonluqlarını götürərək sonluq massivini yaradaq:
s[1..n], s[2..n], ..., s[n..n]
və onları leksikoqrafik qaydada sıralayaq. Nəticədə sıralanmış sonluqlar siyahısını əldə edəcəyik:
s[p(1)..n], s[p(2)..n], ..., s[p(n)..n]
burada p(1), p(2), ..., p(n) ardıcıllığı s[1..n] mətninin sonluq massivi adlanır. Məsələn, əgər s = abbaabab olarsa, sıralanmış sonluqlar siyahısı belə olacaq:
aabab, ab, abab, abbaabab, b, baabab, bab, bbaabab
və sonluq massivi belə olacaq: 4, 7, 5, 1, 8, 3, 6, 2.
Belə bir massiv xətti vaxtda qurula bilər. Sizin vəzifəniz isə bunun əksini etməkdir: verilmiş p(1), p(2), p(3), ..., p(n) ardıcıllığı üçün ən azı bir ingilis əlifbasının böyük hərflərindən ibarət mətnin mövcud olub-olmadığını yoxlamaqdır ki, verilmiş ardıcıllıq həmin mətnin sonluq massivi olsun. Əgər belə bir mətn mövcuddursa, onlardan birini çıxış edin. Əks halda, -1 çıxış edin.
Giriş verilənləri
Giriş məlumatları bir neçə sonluq massivi təsvirini ehtiva edir. Birinci sətir testlərin sayını t (t ≤ 100) ehtiva edir. Hər bir təsvir mətnin və massivinin uzunluğunu n (1 ≤ n ≤ 500000) ehtiva edən sətirlə başlayır. Növbəti sətir tam ədədləri p(1), p(2), ..., p(n) ehtiva edir. Qəbul edin ki, 1 ≤ p(i) ≤ n və hər bir p(i) dəyəri iki dəfə təkrarlanmır. Giriş məlumatlarının ölçüsü 50 MB-dan çox deyil.
Çıxış verilənləri
Hər bir test üçün verilmiş sonluq massivinə uyğun olan istənilən bir mətn çıxış edin. Əgər böyük hərflərdən ibarət ingilis əlifbası ilə uyğun mətn mövcud deyilsə, -1 çıxış edin.