在年輕的時(shí)候，我們故事中的英雄——國(guó)王 Copa——他的私人數(shù)據(jù)并不是完全安全地隱蔽。對(duì)他來(lái)說(shuō)是，這不可接受的。因此，他發(fā)明了一種密碼，好記又難以破解。后來(lái)，他才知道這種密碼是一個(gè)長(zhǎng)度為奇數(shù)的回文串。

Copa 害怕忘記密碼，所以他決定把密碼寫在一張紙上。他發(fā)現(xiàn)這樣保存密碼不安全，于是他決定按下述方法加密密碼：他選定一個(gè)整數(shù) X ，保證 X 不小于 0 ，且 2X 嚴(yán)格小于串長(zhǎng)度。然后他把密碼分成 3 段，最前面的 X 個(gè)字符為一段，最后面的 X 個(gè)字符為一段，剩余的字符為一段。不妨把這三段依次稱之為 prefix, suffix, middle 。顯然， middle 的長(zhǎng)度為一個(gè)大于 0 的奇數(shù)，且 prefix 、 suffix 的長(zhǎng)度相等。他加密后的密碼即為 A + prefix + B + middle + C + suffix ，其中 A 、 B 、 C 是三個(gè)由 Copa 選定的字符串，且都有可能為空， + 表示字符串相連。

許多年過(guò)去了。Copa 昨天找到了當(dāng)年寫下加密后字符串的那張紙。但是，Copa 把原密碼、A、B、C 都忘了。現(xiàn)在，他請(qǐng)你找一個(gè)盡量長(zhǎng)的密碼，使得這個(gè)密碼有可能被當(dāng)年的 Copa 發(fā)明、加密并寫下。

輸入包含一個(gè)只含有小寫拉丁字母的字符串，長(zhǎng)度在 1 到 10^5 之內(nèi)。

第一行包含一個(gè)整數(shù) k ，表示你找到的原密碼分成的 3 個(gè)部分中有多少個(gè)非空字符串。顯然 k in {1, 3} 。接下來(lái) k 行，每行 2 個(gè)用空格分開(kāi)的整數(shù) x_i l_i ，表示這一部分的起始位置和長(zhǎng)度。要求輸出的 x_i 遞增。
起始位置 x_i 應(yīng)該在 1 到加密后的字符串長(zhǎng)度之間。 l_i 必須是正整數(shù)，因?yàn)槟阒灰敵龇强詹糠值男畔ⅰ?middle 的長(zhǎng)度必須為奇數(shù)。
如果有多組答案，任意一組即可。提示：你要最大化的是輸出的 l_i 的總和，而不是 k 。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

藍(lán)橋杯