Davamlı siyahı
Verilmiş n ədədindən ibarət bir siyahı var. Aşağıdakı əməliyyatları yerinə yetirməyi öyrənməlisiniz:
merge — İki mövcud siyahını birləşdirərək onların konkatenasiyasına bərabər yeni bir siyahı yaradın.
head — Mövcud bir siyahı L götürərək, iki yeni siyahı yaradın: birincisi L-in ilk elementini, ikincisi isə L-in ilk elementi istisna olmaqla qalan hissəsini ehtiva edir.
tail — Mövcud bir siyahı L götürərək, iki yeni siyahı yaradın: birincisi L-in son elementi istisna olmaqla qalan hissəsini, ikincisi isə L-in son elementini ehtiva edir.
Yeni yaradılmış siyahılar üçün onların elementlərinin cəmini 10^9 + 7 modulu ilə hesablamalısınız.
Giriş verilənləri
Əvvəlcə n (1 ≤ n ≤ 10^5) ədədi verilir. Daha sonra 1 ilə 10^9 arasında olan n tam ədəd - siyahıların elementləri verilir. Əsas siyahılar 1, 2, ..., n nömrələrinə malikdir.
Sonra m (1 ≤ m ≤ 10^5) ədədi - əməliyyatların sayı verilir. Əməliyyatlar aşağıdakı formatda təqdim olunur:
merge i j
head i
tail i
burada i və j artıq mövcud olan siyahıların nömrələridir. Əgər hazırda k siyahı varsa, yeni siyahı k+1 nömrəsini alır.
head və tail əməliyyatları üçün əvvəlcə sol hissə, sonra sağ hissə yaradılır (nümunəyə baxın). Sizə zəmanət verilir ki, heç vaxt boş siyahılar yaradılmayacaq.
Çıxış verilənləri
Hər yeni siyahı üçün elementlərin cəmini 10^9 + 7 modulu ilə çap etməlisiniz.