Təlimat
İnqrid böyük bir dəmir yolu stansiyasının rəhbəridir və onun əsas vəzifələrindən biri qatarların platformalar üzrə hərəkətini idarə etməkdir. Stansiyanın yalnız bir girişi var və qatarları müxtəlif keçidlərə və platformalara yönləndirən keçidlər mövcuddur.
Hər keçidin bir girişi və iki çıxışı var, platformaların isə yalnız bir girişi var. Stansiyanın girişi bir çıxışa malikdir. Hər bir çıxış bir girişə və əksinə bağlıdır. Stansiyanın girişindən hər hansı bir keçidə və ya platformaya çatmaq mümkündür.
Platformalar dalanlarla bitir. Qatarların platformaya çatdıqdan dərhal sonra platformadan yox olduğunu hesab edin.
Hər səhər İnqrid cədvələ baxır və keçid təlimatlarını yazır: hansı vaxtda və hansı keçidi dəyişmək lazımdır. O, bu prosesi avtomatlaşdırmaq istəyir ki, çox vaxt qənaət etsin.
Giriş məlumatları
Birinci sətir stansiyadakı keçidlərin və platformaların ümumi sayını n (3 ≤ n ≤ 51) ehtiva edir.
Sonrakı n sətirdən hər biri i nömrəli keçidi və ya platformanı təsvir edir. Təsvir platforma üçün p simvolu ilə və ya keçid üçün s simvolu ilə başlayır. Növbəti rəqəm q[i] (0 ≤ q[i] < i) onun qoşulduğu keçidin giriş yolunun nömrəsini və ya stansiyanın girişinə qoşulmuşsa 0 göstərir. Platformanın təsviri həmçinin unikal kiçik ingilis hərfi - platformanın identifikatorunu ehtiva edir.
Qatarların iki qoşulmuş keçid və ya keçid və platforma arasında hərəkət etməsi üçün dəqiq bir dəqiqə lazımdır. Səhər hər keçid elə dəyişdirilir ki, qatar keçidə/platformaya qoşulmuş iki çıxış yolundan daha aşağı nömrəli olanına keçsin.
Növbəti sətir cədvəldəki qatarların sayını m (1 ≤ m ≤ 1000) ehtiva edir.
Sonrakı m sətirdən hər biri bir tam ədəd a[i] (0 ≤ a[i] ≤ 10 000, a[i] > a[i-1]) - qatarın stansiyanın girişinə gəldiyi dəqiqə və p[i] hərfi - bu qatar üçün təyinat platformasının identifikatorunu ehtiva edir.
Çıxış məlumatları
Birinci sətirdə keçid dəyişikliklərinin əmrlərinin sayını c tam ədəd olaraq verin. Hər bir əmr üçün iki tam ədəd s[i] və t[i] (1 ≤ s[i] ≤ n, 0 ≤ t[i] ≤ 10^9) - keçidin nömrəsi və onun nə vaxt dəyişdirilməli olduğunu verin. Dəyişiklik t[i] - 1 və t[i] dəqiqələri arasında baş verir.
Əmrləri vaxtın azalan ardıcıllığı ilə verin. Əmrlərin sayı 100 000-i keçməməlidir.
Nümunə
Aşağıda birinci nümunə üçün vaxt qrafiki verilmişdir.
