SPOJ in Armenian

Շարադրանք

Գևորգն ունի s տողը, որն իրենից ներկայացնում է անգլերեն փոքրատառերից կազմված հաջորդականություն։ Նա որոշել է ստանալ նոր տող իր ունեցած տողից հետևյալ կերպ. նա վերցնում է սկզբնական տողի որևէ տառեր և, հարաբերական հերթականությունը չփոխելով, գրում է իրար կողք։ Այլ կերպ ասած՝ եթե սկզբնական տողի տառերը նշանակենք si-երով՝ s = s1s2...sn, ապա Գևորգն ընտրում է որևէ k թիվ, 1 ≤ i1 < i2 < ... < ik ≤ n ինդեքսներ և ստանում նոր տող՝ si1si2...sik։ Այդպես, օրինակ, abbc տողից կարելի է ստանալ հետևյալ տողերը՝ a, b, c, ab, ac, bb, bc, abb, abc, bbc և abbc։ Նրա նպատակն է ստանալ այնպիսի նոր տող, որը հանդիսանա սկզբնական տողի նախածանց։ Բայց կա մի պայման. չպետք է վերցված բոլոր տառերը s-ի k երկարության նախածանցից լինեն, այսինքն  չպետք է տեղի ունենա հետևյալ պայմանը՝ (i1, i2, ... ik) = (1, 2, ..., k)։

Օգնեք Գևորգին գտնել այդպիսի ամենաերկար հնարավոր նոր տողը։ Հարկավոր է արտածել k թիվը և i1, i2, ..., ik ինդեքսները։ Եթե ոչ մի նոր տող չի հանդիսանում սկզբնականի նախածանց, ապա բավական է ընդամենը արտածել 0 թիվը։

Հիշեցում՝ տողի նախածանցը տող է, որը ստացվում է սկզբնական տողից՝ աջից ջնջելով որոշ քանակի (հնարավոր է 0 հատ) սիմվոլներ։ Օրինակ՝ abac-ի նախածանցներն են a-ն, ab-ն, aba-ն, և abac-ն։

Մուտքային տվյալներ

Մուտքի միակ տողում տրված է s տողը (1 ≤ s.length ≤ 2⋅105)։

Ելքային տվյալներ

Ելքում պետք է արտածել k թիվը և ինդեքսների i1, i2, ..., ik հաջորդականությունը՝ անջատված մեկական բացատանիշերով։

Օրինակ

Բացատրություն

Վերջին օրինակում կարելի է նաև արտածել (1, 2, 6) և (1, 4, 6) եռյակները։