题目描述

给定两个正整数 $M$ 和 $N$。

我们使用英文字母表中前 $M$ 个大写字母，即

A, B, C, ...

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

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

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

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

沿顺时针方向得到的四个长度为 $2$ 的字符串依次为：

AA, AB, BB, BA

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

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

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

• 令 $P$ 为字典序最小的字符串；
• 令 $Q$ 为字典序最大的字符串。

例如，当 $M=2,N=2$ 时：

• $P=$ AABB；
• $Q=$ BBAA。

现在给定 $X$ 个长度均为 $N$ 的查询字符串。对于每个查询字符串 $S$，请分别求出它在 $P$ 和 $Q$ 中出现的起始位置。

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

位置从 $0$ 开始编号。

输入格式

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

第二行包含一个整数 $X$，表示查询字符串的个数。

接下来 $X$ 行，每行包含一个长度恰好为 $N$ 的字符串，只由前 $M$ 个大写英文字母组成。

输出格式

输出 $X$ 行。

对于每个查询字符串 $S$，输出两个整数 $p,q$：

• $p$ 表示 $S$ 在 $P$ 中出现的起始位置；
• $q$ 表示 $S$ 在 $Q$ 中出现的起始位置。

位置均从 $0$ 开始编号。

数据范围

因此

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

样例

输入

2 2
3
AA
AB
BA

输出

0 2
1 3
3 1

样例解释

当 $M=2,N=2$ 时：

P = AABB
Q = BBAA

把字符串看成圆环：

• AA 在 $P$ 中从位置 $0$ 开始，在 $Q$ 中从位置 $2$ 开始；
• AB 在 $P$ 中从位置 $1$ 开始，在 $Q$ 中从位置 $3$ 开始，其中 $Q$ 的这次出现跨过字符串末尾；
• BA 在 $P$ 中从位置 $3$ 开始，在 $Q$ 中从位置 $1$ 开始。