A boy named Ayrat lives on planet AMI-1511. Each inhabitant of this planet has a talent. Specifically, Ayrat loves running, moreover, just running is not enough for him. He is dreaming of making running a real art.
First, he wants to construct the running track with coating
t. On planet AMI-1511 the coating of the track is the sequence of colored blocks, where each block is denoted as the small English letter. Therefore, every coating can be treated as a string.
Unfortunately, blocks aren't freely sold to non-business customers, but Ayrat found an infinite number of coatings
s. Also, he has scissors and glue. Ayrat is going to buy some coatings
s, then cut out from each of them
exactly one continuous piece (substring) and glue it to the end of his track coating. Moreover, he may choose to flip this block before glueing it. Ayrat want's to know the minimum number of coating
s he needs to buy in order to get the coating
t for his running track. Of course, he also want's to know some way to achieve the answer.
一个名叫艾拉特的男孩生活在AMI-1511星球上。这个星球上的每个居民都有天赋。具体来说,艾拉特喜欢跑步,而且,仅仅跑步对他来说是不够的。他梦想着让跑步成为一门真正的艺术。
首先,他想用涂层t建造跑道。在行星AMI-1511上,轨道的涂层是彩色块的序列,其中每个块都表示为小英文字母。因此,每个涂层都可以被视为一根绳子。
不幸的是,块不能免费出售给非商业客户,但Ayrat发现了无数的涂料。此外,他还有剪刀和胶水。Ayrat 打算购买一些涂层,然后从每个涂层中切出一块连续的(子串),并将其粘在他的轨道涂层的末端。此外,他可以选择在粘合之前翻转这个块。Ayrat 想知道他需要购买的涂层的最低数量,以便为他的跑道获得涂层。当然,他也想知道一些方法来实现答案。
Output
The first line should contain the minimum needed number of coatings
n or
-1 if it's impossible to create the desired coating.
If the answer is not
-1, then the following
n lines should contain two integers
xi and
yi− numbers of ending blocks in the corresponding piece. If
xi≤yi then this piece is used in the regular order, and if
xi>yi piece is used in the reversed order. Print the pieces in the order they should be glued to get the string
t.
Note
In the first sample string "
cbaabc" = "
cba" + "
abc".
In the second sample: "
ayrat" = "
a" + "
yr" + "
at".