Agentlik
Bir çox uçuş axtarış startaplarının izindən gedərək, ilk planetlərarası səyahət veb saytını yaratmaq istəyirsiniz. İlk probleminiz iki planet arasında səyahət etmək üçün ən ucuz yolu tez tapmaqdır. Rəqiblərinizə qarşı üstünlüyünüz var, çünki bütün planetlərin və onların arasındakı uçuşların xüsusi bir struktura malik olduğunu başa düşmüsünüz. Hər bir planet N bitdən ibarət bir sətirlə təmsil olunur və iki planet arasında uçuş var, əgər onların N-bitlik sətirləri yalnız bir mövqedə fərqlənirsə.
Uçuşun dəyəri, təyinat planetinə enişin dəyəridir. Əgər planetin sətirindəki i-ci simvol 1dirsə, o zaman i-ci vergi eniş üçün ödənilməlidir. Bir planetə enişin dəyəri tətbiq olunan vergilərin cəmidir.
Başlanğıc planet, son planet və i-ci verginin dəyəri verildikdə, başlanğıc planetdən son planetə çatmaq üçün ən ucuz uçuşlar dəstini hesablayın.
Giriş verilənləri
Hər bir test üçün giriş iki sətirdən ibarət olacaq. Birinci sətirdə N (1 ≤ N ≤ 1000), planetləri təmsil edən bitlərin sayı; S, başlanğıc planetini təmsil edən sıfır və birlərdən ibarət N uzunluğunda bir sətir; və eyni formatda son planetini təmsil edən E sətiri olacaq. İkinci sətirdə N ədəd olacaq, bunlardan i-ci, i-ci verginin dəyəridir. Bütün xərclər 1 ilə 1000000 arasında olacaq. Giriş bir tək 0 olan sətirlə bitəcək.
Çıxış verilənləri
Hər bir test üçün başlanğıc planetdən son planetə çatmaq üçün minimum dəyəri aşağıda verilmiş formatda çıxarın.