Kriptoqrafiya
Gənc kriptoanalitik Corc, dostu Endryunun icad etdiyi yeni şifrəni sındırmaq istəyir. Bunun üçün o, Z_r = Z/rZ halqası üzərində bir neçə xətti çevrilmə həyata keçirməlidir.
Hər bir xətti çevrilmə 2x2 matrisi ilə təyin olunur. Corcun əlində A_1, A_2, ..., A_n matrislər ardıcıllığı var. Alqoritmin hər addımında, bu ardıcıllığın müəyyən bir A_i, A_{i+1}, ..., A_j seqmentini seçməli və bir vektoru P_{i,j} = A_i×A_{i+1}×...×A_j hasilinə vurmalıdır. Bu əməliyyatı m müxtəlif seqment üçün yerinə yetirməlidir. Corca lazım olan hasilatları tapmağa kömək edin.
Giriş verilənləri
Birinci sətir r (1 ≤ r ≤ 10000), n (1 ≤ n ≤ 30000) və m (1 ≤ m ≤ 30000) dəyərlərini ehtiva edir. Sonrakı n blok iki sətirdən ibarətdir və hər biri 0 dan r - 1 aralığında olan iki tam ədəd ehtiva edir, matrisləri təyin edir. Bloklar bir-birindən boş sətirlə ayrılır. Daha sonra m cüt tam ədəd gəlir, hər biri 1 dən nə qədər olan aralıqda, hansı seqmentdə hasilatın hesablanacağını göstərir.
Çıxış verilənləri
m blok çıxarın, hər biri iki sətirdən ibarətdir. Hər sətir 0 dan r - 1 aralığında olan iki tam ədəd ehtiva edir, beləliklə hasilat matrisini təşkil edir.
Blokları boş sətirlə ayırın.