#P3538. [POI 2012] OKR-A Horrible Poem

[POI 2012] OKR-A Horrible Poem

题目描述

Byteie boy has to learn a fragment of a certain poem by heart. The poem, following the best lines of modern art, is a long string consisting of lowercase English alphabet letters only. Obviously, it sounds horrible, but that is the least of Byteie's worries. First and foremost, he completely forgot which fragment is he supposed to learn. And they all look quite difficult to memorize...

There is hope, however: some parts of the poem exhibit certain regularity. In particular, every now and then a fragment, say AA, is but a multiple repetition of another fragment, say BB (in other words, A=BBBA = BB\cdots B, i.e., A=BkA = B^k, where k1k\geq1 is an integer). In such case we say that BB is a full period of AA (in particular, every string is its own full period). If a given fragment has a short full period, Byteie's task will be easy. The question remains... which fragment was that?

Make a gift for Byteie - write a program that will read the whole poem as well as a list of fragments that Byteie suspects might be the one he is supposed to memorize, and for each of them determines its shortest full period.

输入格式

In the first line of the standard input there is a single integer nn (1n500,0001\leq n\leq500,000). In the second line there is a string of length nn consisting of lowercase English alphabet letters - the poem. We number the positions of its successive characters from 11 to nn.

The next line holds a single integer qq (1q2,000,0001\leq q\leq2,000,000) denoting the number of fragments. Then the following qq lines give queries, one per line. Each query is a pair of integers aia_i and bib_i (1aibin1\leq a_i\leq b_i\leq n), separated by a single space, such that the answer to the query should be the length of the shortest full period of the poem's fragment that begins at position aia_i and ends at position bib_i.

In tests worth in total 42% of the points n10,000n\leq10,000 holds in addition. In some of those, worth 30% of points in total, q10,000q\leq10,000 holds as well.

输出格式

Your program should print qq lines on the standard output. The ii - th of these lines should hold a single integer - the answer to the ii - th query.

8
aaabcabc
3
1 3
3 8
4 8
1
3
5