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}\} $ .

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 $ .

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] $ .