This is the hard version of the problem. The difference between the versions is that in this version, the constraints on $k$ and $q$ are larger. 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}\}$.

Input

The first line of the input contains two integers $k$ and $q$ ($2\le k\le 62$, $1\le q\le 10^4$) — 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$.

Output

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

Note

Denote the substring $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]$.