54. 十字騎士與危險的陷阱

題目敘述

一個由魔力無盡的女神、使用強大爆裂魔法的魔法師、上級職業十字騎士、與一個普通的鬼畜冒險者和真組成的隊伍，某天因為接下了某個任務，而進到了一座無人探索的古城之中。 但是因為一個不小心，他們卻觸發了危險的陷阱。身為十字騎士，懷抱著大愛、情懷、犧牲小我、絕對的堅忍防禦、慈悲與M屬性的達克尼絲，自告奮勇地衝向了陷阱，讓她自己一個人被關在陷阱之中，好讓其他三個人得救。

當然，陷阱一定有其破解方法，在陷阱房間中的一面牆上，寫著一個只由大小寫英文字母組成的字串$S$。對於字串$S$的每個前綴，找出該前綴出現在字串$S$自身的次數，全部加起來之後的數字寫在牆上，如果正確即可逃離陷阱，但若答錯了則會遭受到生不如死的懲罰。 例如：字串$abab$，其前綴有$a、ab、aba、abab$。其中$a$出現2次，$ab$出現2次，$aba$與$abab$各出現1次，全部加起來是6次，則答案是6。

你做為程式設計詩人剛好路過這裡，為了享受逃離這可怕的陷阱，達克尼絲請你幫幫她算出答案，好讓她可以得到正確答案，如此一來她就可以一直回答錯誤以享受生不如死的懲罰逃出陷阱。

輸入

每筆測資的輸入只有一行，只包含一個字串$S$。

$1\le \text{length of }S\le 10^6$

輸出

輸出一個數字：對於字串$S$的每個前綴，找出該前綴出現在字串$S$自身的次數，全部加起來。

Sample I/O

Input

ababaca

Output

12

Judge Setting

run-time limit: 1000 ms
memory limit: 104857600 byte
測資數量: 5