DNT-nin deşifrə edilməsi
Birinci sətirdə n - yerinə yetirilməsi lazım olan əməliyyatların sayı verilir (1 ≤ n ≤ 100 000).
Sonrakı n sətirdə əməliyyatların təsviri verilir. Əgər i-ci sətir "+" simvolu ilə başlayırsa, bu əməliyyat G dəstinə yeni gen əlavə etməkdir. Əgər "?" simvolu ilə başlayırsa, bu əməliyyat D massivinin sonuna yeni DNT zənciri əlavə etməkdir. Daha sonra boşluqla ayrılmış x[i] sətiri verilir, bu sətirdən s[i] sətirini əldə etmək lazımdır. Bu sətir həmin əməliyyatda əlavə edilən gen və ya DNT zəncirini təyin edir.
x[i] sətirindən s[i] sətirini əldə etmək üçün aşağıdakı addımları yerinə yetirmək lazımdır. Əgər i = 1-dirsə, s[i] = x[i]. Əks halda, əvvəlki əməliyyatdan sonra ilk dəfə deşifrə edilən DNT zəncirlərinin sayı k[i-1]-ə bərabərdir. k[i-1] dəfə aşağıdakı addımı yerinə yetiririk: x[i] sətirinin ilk simvolunu sona keçiririk. Başqa sözlə, x[i] sətirini sola k[i-1] dəfə dövrü sürüşdürürük. Alınan sətir s[i]-dir - bu, i-ci əməliyyatda əlavə edilməli olan gen və ya DNT zənciridir.
Bütün sətirlər boş deyil, bütün əməliyyatlarda sətirlərin ümumi ölçüsü 10^6-dan çox deyil. Heç bir anda iki gen mövcud deyil ki, biri digərinin prefiksi olsun.
Çıxış Məlumatları
n sətir çıxarın.
i-ci sətirdə əvvəlcə k[i] - D massivində olan və i-ci əməliyyatdan sonra ilk dəfə deşifrə edilə bilən DNT zəncirlərinin sayı, sonra isə k[i] ədəd - bu zəncirlərin nömrələri verilir. Zəncirlər D massivinə əlavə edilmə sırasına görə birdən başlayaraq nömrələnir. Bir sətirdə zəncir nömrələrini istənilən qaydada çıxarmaq olar.