#P16875. [INSOMNIA 2010]Magic Circle

[INSOMNIA 2010]Magic Circle

题目描述

给定两个正整数 MM 和 NN。

我们使用英文字母表中前 MM 个大写字母,即

A, B, C, ...

将恰好 MNM^N 个字母首尾相接地放在一个圆环上,并要求:从圆环上的任意一个位置开始,沿顺时针方向连续读取 NN 个字母,所得到的 MNM^N 个长度为 NN 的字符串两两不同。

由于使用的字符集大小为 MM,长度为 NN 的字符串总数也恰好为 MNM^N,因此这等价于:每一个由前 MM 个大写字母组成的长度为 NN 的字符串,都在圆环上恰好出现一次。

例如,当 M=2,N=2M=2,N=2 时,可以得到如下圆环:

M=2,N=2 的一个 Magic Circle

沿顺时针方向得到的四个长度为 22 的字符串依次为:

AA, AB, BB, BA

注意最后一个 BA 会跨过线性字符串的末尾,从末尾的 B 继续读到开头的 A。

对于任意一个合法圆环,我们可以任选圆环上的一个位置作为起点,把整个圆环写成一个长度为 MNM^N 的普通字符串。

在所有合法圆环以及所有起点所得到的字符串中:

  • 令 PP 为字典序最小的字符串;
  • 令 QQ 为字典序最大的字符串。

例如,当 M=2,N=2M=2,N=2 时:

  • P=P= AABB;
  • Q=Q= BBAA。

现在给定 XX 个长度均为 NN 的查询字符串。对于每个查询字符串 SS,请分别求出它在 PP 和 QQ 中出现的起始位置。

这里仍然把 PP 和 QQ 看作首尾相接的圆环,因此一次长度为 NN 的匹配可以跨过字符串末尾并从开头继续。

位置从 00 开始编号。

输入格式

第一行包含两个整数 M,NM,N。

第二行包含一个整数 XX,表示查询字符串的个数。

接下来 XX 行,每行包含一个长度恰好为 NN 的字符串,只由前 MM 个大写英文字母组成。

输出格式

输出 XX 行。

对于每个查询字符串 SS,输出两个整数 p,qp,q:

  • pp 表示 SS 在 PP 中出现的起始位置;
  • qq 表示 SS 在 QQ 中出现的起始位置。

位置均从 00 开始编号。

数据范围

1≤M≤10,1\le M\le 10, 1≤N≤7.1\le N\le 7.

因此

MN≤107.M^N\le 10^7.

原题未在题面中给出 XX 的额外上界。

样例

输入

2 2
3
AA
AB
BA

输出

0 2
1 3
3 1

样例解释

当 M=2,N=2M=2,N=2 时:

P = AABB
Q = BBAA

把字符串看成圆环:

  • AA 在 PP 中从位置 00 开始,在 QQ 中从位置 22 开始;
  • AB 在 PP 中从位置 11 开始,在 QQ 中从位置 33 开始,其中 QQ 的这次出现跨过字符串末尾;
  • BA 在 PP 中从位置 33 开始,在 QQ 中从位置 11 开始。