1s, 32MB

Pak Dengklek bersama tim risetnya sedang mengembangkan program untuk mereduksi pesan yang berupa sederetan huruf alfabet kapital (A – Z). Program ini sudah selesai dikembangkan, dan kini memasuki tahap pengujian. Sayangnya, Pak Dengklek dan tim kebingungan bagaimana memastikan bahwa program yang mereka kembangkan bekerja dengan baik. Akhirnya ia meminta bantuan Anda untuk membuat program yang dapat membantu mengoreksi pekerjaan Pak Dengklek.

Program yang diinginkan Pak Dengklek sederhana. Anda akan diberikan sebuah untaian pesan berisi simbol A – Z (semua kapital) tanpa spasi. Setiap huruf akan dinomori 1 sampai N, dengan N adalah panjang dari pesan itu sendiri. Kemudian Pak Dengklek akan memberikan beberapa pertanyaan yang dinyatakan oleh pasangan bilangan i dan j. Program anda harus mengeluarkan hasil reduksi substring dari posisi ke-i hingga posisi ke-j. Adapun aturan reduksi yang diinginkan adalah sebagai berikut:

Untuk setiap sekumpulan huruf yang saling bersebelahan dan memiliki simbol yang sama, hapus semua kecuali satu. Dengan kata lain, pada hasil reduksi pesan, tidak ada dua huruf yang sama akan saling bersebelahan. Contoh: HAALLLLLOOOOO ? HALO, MATARAM ? MATARAM, dan AAAAA ? A.
Hitung panjang pesan setelah dilakukan proses reduksi. Keluarkan angka ini, karena ini merupakan informasi yang penting untuk Pak Dengklek. Contoh: HAALLLLLOOOOO ? HALO (4 huruf).
Jika panjang pesan yang tereduksi lebih kecil dari 10, cetak juga pesan hasil reduksi tersebut.
Bisakah Anda menyelesaikan program yang diinginkan Pak Dengklek? Sebagai catatan, Pak Dengklek hanya memberikan Anda sedikit waktu karena sebentar lagi hasil penelitian mereka akan dipublikasikan.

Format Masukan

Pada baris pertama, program Anda akan menerima label kasus uji. Label kasus uji berisi sebuah string yang dijelaskan sebagai berikut:

Panjang string tersebut adalah banyaknya subsoal ditambah satu.
Digit pertama dari label adalah karakter ke-0, digit kedua dari label adalah karakter ke-1, dan seterusnya.
Karakter ke-0 akan berisi 0 jika kasus uji tersebut merupakan contoh kasus uji, atau berisi '.' jika bukan.
Untuk setiap nilai i di antara 1 hingga banyaknya subsoal, berlaku:
jika kasus uji tersebut memenuhi batasan subsoal ke-i, maka karakter ke-i berisi i, atau
jika kasus uji tersebut tidak memenuhi batasan subsoal ke-i, maka karakter ke-i berisi karakter '.'
Sebagai contoh apabila label sebuah kasus uji sebuah soal adalah 0..345, maka:

Soal tersebut memiliki 5 buah subsoal,
Kasus uji tersebut merupakan contoh kasus uji, dan
Kasus uji tesebut memenuhi batasan subsoal ke-3, ke-4, dan ke-5.
Baris kedua berisi 2 bilangan, N dan Q, dimana N adalah panjang pesan dan Q adalah banyaknya pertanyaan.

Baris berikutnya adalah sebuah pesan yang terdiri dari simbol A – Z, sepanjang N.

Q baris berikutnya berisi 2 buah bilangan i dan j.

Format Keluaran

Untuk setiap pertanyaan, keluarkan panjang pesan setelah melakukan reduksi potongan pesan dari posisi ke-i hingga posisi ke-j. Apabila panjang pesan lebih kecil dari 10, maka tampilkan hasil reduksinya di baris yang sama dipisahkan oleh spasi.

Contoh Masukan

0..345
20 5
AAABBCCCCCQWERTYUIOP
1 1
1 3
2 9
1 20
18 20

Contoh Keluaran

1 A
1 A
3 ABC
13
3 IOP

Subsoal

Subsoal 1 (7 poin)

• N = 15
• Q = 10
• Kasus uji dapat diunduh di sini.

Subsoal 2 (11 poin)

• N = 100
• Q = 10
• Kasus uji dapat diunduh di sini.

Subsoal 3 (21 poin)

• 1 ? N ? 100
• 1 ? Q ? 100

Subsoal 4 (27 poin)

• 1 ? N ? 100
• 1 ? Q ? 100.000

Subsoal 5 (34 poin)

• 1 ? N ? 100.000
• 1 ? Q ? 100.000