CF2249E1.String (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, the constraints on $k$ and $q$ are smaller. You can hack only if you solved all versions of this problem.

Define $\mathrm{popcount}_k(m)$ as the sum of all digits of $m$ in base $k$.

Define a base-$k$ integer $s=\overline{s_1s_2\cdots}$ of infinite length, where the $i$-th digit of $s$ is $s_i=(\mathrm{popcount}_k(i) \bmod k)$.

There are $q$ queries. Each query consists of three integers $l$, $r$, and $n$ (all of them are given in decimal form), as well as a base-$k$ integer $t$ with $n$ digits. Note that $t$ may have leading zeros. Consider $t$ as a string, and your task is to find the number of occurrences of $t$ in the string $s_ls_{l+1}\ldots s_r$.

For digits greater than or equal to decimal $\mathtt{10}$, uppercase and lowercase letters are used. Specifically, the uppercase letters ${\mathtt{A, B,\ldots,Z}}$ represent the decimal values ${\mathtt{10, 11,\ldots,35}}$, and the lowercase letters ${\mathtt{a, b,\ldots,z}}$ represent the decimal values ${\mathtt{36, 37,\ldots,61}}$.

这是该问题的简单版本。两个版本的区别在于，本版本中 $k$ 和 $q$ 的约束更小。仅当您解决了该问题的所有版本时，才允许进行 hack。

定义 $\mathrm{popcount}_k(m)$ 为 $m$ 在 $k$ 进制下的各位数字之和。

定义一个长度无限的 $k$ 进制整数 $s=\overline{s_1s_2\cdots}$，其中 $s$ 的第 $i$ 位数字为 $s_i=(\mathrm{popcount}_k(i) \bmod k)$。

共有 $q$ 个查询。每个查询包含三个整数 $l$、$r$ 和 $n$（均以十进制给出），以及一个长度为 $n$ 的 $k$ 进制整数 $t$。注意：$t$ 可能含有前导零。将 $t$ 视为一个字符串，您的任务是求出 $t$ 在字符串 $s_ls_{l+1}\ldots s_r$ 中出现的次数。

对于大于等于十进制 $\mathtt{10}$ 的数字，使用大写和小写字母表示。具体而言，大写字母 ${\mathtt{A, B,\ldots,Z}}$ 分别表示十进制数值 ${\mathtt{10, 11,\ldots,35}}$，小写字母 ${\mathtt{a, b,\ldots,z}}$ 分别表示十进制数值 ${\mathtt{36, 37,\ldots,61}}$。

The first line of the input contains two integers $k$ and $q$ ($2\le k\le 10$, $1\le q\le 1000$) — the base and the number of queries.

Each query contains two lines. The first line contains the three integers $l$, $r$, and $n$ ($1\le l\le r\le 10^{17}$, $1\le n\le 2\cdot 10^6$).

The second line contains the base-$k$ integer $t$ with $n$ digits ($t_i\in{\mathtt{0,1,\ldots,9,A,B,\ldots,Z,a,b,\ldots,z}}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^6$.

输入的第一行包含两个整数 $k$ 和 $q$（$2\le k\le 10$，$1\le q\le 1000$）—— 分别表示进制基数和查询次数。

每个查询包含两行。第一行包含三个整数 $l$、$r$ 和 $n$（$1\le l\le r\le 10^{17}$，$1\le n\le 2\cdot 10^6$）。

第二行包含一个长度为 $n$ 的 $k$ 进制整数 $t$（其各位数字 $t_i$ 属于集合 $\{\mathtt{0,1,\ldots,9,A,B,\ldots,Z,a,b,\ldots,z}\}$）。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^6$。

For each query, output a single integer — the answer to the query.

对于每个查询，输出一个整数——该查询的答案。

Denote the string $s_ls_{l+1}\ldots s_r$ as $s[l;r]$.

In the first example, $k = 3$, $s = \mathtt{12120201120201012201120012\ldots}$, $s[5;17] = \mathtt{0201120201012}$, and $t = \mathtt{201}$ appears a total of $2$ times in $s[5; 17]$. Their indices in the string $s$ are $s[6; 8]$ and $s[12; 14]$. And $t = \mathtt{01}$ appears $3$ times. Their indices in the string $s$ are $s[7;8]$, $s[13;14]$, and $s[15;16]$.

For the second example, $k=10$, $s[1;20] = \mathtt{12345678912345678902}$, and $t = \mathtt{123456789}$ appears a total of $2$ times in $s[1;20]$.

记字符串 $s_ls_{l+1}\ldots s_r$ 为 $s[l;r]$。

在第一个例子中，$k = 3$，$s = \mathtt{12120201120201012201120012\ldots}$，$s[5;17] = \mathtt{0201120201012}$，而 $t = \mathtt{201}$ 在 $s[5; 17]$ 中共出现 $2$ 次，其在字符串 $s$ 中的起始位置分别为 $s[6; 8]$ 和 $s[12; 14]$；而 $t = \mathtt{01}$ 共出现 $3$ 次，其在字符串 $s$ 中的起始位置分别为 $s[7;8]$、$s[13;14]$ 和 $s[15;16]$。

在第二个例子中，$k=10$，$s[1;20] = \mathtt{12345678912345678902}$，而 $t = \mathtt{123456789}$ 在 $s[1;20]$ 中共出现 $2$ 次。