DJ Nicholas 是一位在圣诞节和新年活动中广受欢迎的 DJ。DJ Nicholas 有一套经过实战检验的播放列表制作流程，但他需要帮助来准备这些列表。他的实战流程如下：

首先，他拥有 $k$ 段简短的圣诞歌曲片段。由于 $k$ 最多为 26，他将字母表的前 $k$ 个字母分配给这些歌曲（按它们首次播放的顺序）。

他通过不断重复这 $k$ 首歌曲的片段来创建一个无限循环的主音轨 $t$。为了防止音轨过于单调，每当 DJ Nicholas 在主音轨中重复歌曲片段时，他都会先通过将当前的第一首歌移到片段末尾来改变顺序。

例如，如果 $k = 4$，那么他的歌曲片段可以用字符串 ABCD 表示，主音轨 $t$ 可以表示为无限字符串 “ABCD BCDA CDAB DABC ABCD ...”（空格仅为可读性而设，实际并不存在于 $t$ 中）。

他准备的播放列表可以用一个长度为 $n$ 的字符串表示，初始时全部为空白。接下来，他对播放列表执行 $q$ 次操作，每次操作属于以下两种形式之一：

• “+ $i$ $a$ $b$”。这会将播放列表中从 $a$ 到 $b$（包含 $a$ 和 $b$）的歌曲片段替换为 $t$ 中从位置 $i$ 开始、长度为 $b - a + 1$ 的子串。
• “? $a$ $b$”。这会输出 $k$ 个整数；其中第 $j$ 个整数表示在播放列表从 $a$ 到 $b$（包含 $a$ 和 $b$）的范围内，由字母表第 $j$ 个字母所代表的歌曲出现的次数。

DJ Nicholas 需要这些信息来追踪他需要支付的版税。

在此，我们假设主音轨和播放列表均从 1 开始索引。

你可以参考样例输入/输出，查看 DJ Nicholas 的实战流程是如何运作的！

帮助 DJ Nicholas 回答上述查询，并确保他的观众在活动中尽兴而归！

输入格式

输入的第一行包含三个由空格分隔的整数 $k$、$n$ 和 $q$。

接下来 $q$ 行，描述各项操作。每行要么是 “+ $i$ $a$ $b$” 形式，要么是 “? $a$ $b$” 形式，对应上述操作。

输出格式

对于每个 “? $a$ $b$” 形式的操作，输出一行包含 $k$ 个由空格分隔的整数，对应于该查询的答案。

数据范围

$1 \le k \le 26$ $1 \le n \le 10^9$ $1 \le q \le 10^5$ 每次操作中 $1 \le i \le 10^9$ 每次操作中 $1 \le a \le b \le n$

样例

输入 1

4 10 4
+ 7 2 6
+ 2 8 10
+ 9 1 4
? 4 9

输出 1

1 2 1 1

说明

在此，$k = 4$ 且 $n = 10$。因此，$t = \text{ABCDBCDACDABDABC} \dots$

播放列表最初为空，我们用该字符串表示（其中空白用星号表示）：

如果我们执行操作 “+ 7 2 6”，我们会注意到：

• 我们需要一个长度为 $6 - 2 + 1 = 5$ 的子串。
• 这里我们在 $t$ 中高亮显示从位置 7 开始、长度为 5 的子串： $\text{ABCDBCDACDABDABC} \dots$
• 将播放列表中的第 2 到第 6 首歌曲替换为该子串，此时播放列表变为： DACDA*

你可以验证在执行 “+ 2 8 10” 后，我们得到以下字符串： DACDABCD

然后，通过操作 “+ 9 1 4”，我们覆盖了之前的一些歌曲，最终得到： CDABDA*BCD

之后，我们查询 “? 4 9”，因此我们查看当前播放列表中第 4 到第 9 首歌曲： CDABDA*BCD

我们输出的四个整数应该是 A、B、C 和 D 在此范围内当前出现的次数。因此，输出应该是 “1 2 1 1”。