Number

题目描述

You are given a base $B$ and a positive integer $A$. Every non-negative integer is written in base $B$, with leading zeros added so that all numbers involved have enough digits.

For a non-negative integer $x$, let $d_i(x)$ be the $i$-th base-$B$ digit of $x$ counted from the least significant digit (so $d_0(x)$ is the least significant digit). Define

$$h(x) = \bigl|\{\, i \ge 0 : d_i(x) \lt d_i(A) \,\}\bigr|,$$

that is, $h(x)$ is the number of positions at which the base-$B$ digit of $x$ is **strictly smaller** than the corresponding digit of $A$.

You must answer $T$ queries. Each query gives four integers $D, L, R, K$. For that query, count the number of integers $x$ satisfying **both** of the following conditions:

1. $L \le x$ and $x + D \le R$; 2. $h(x) = K$ and $h(x + D) = K$.

Constraints

• $10 \le B \le 100$
• $1 \le A \le 10^{18}$
• $1 \le T \le 5000$
• $1 \le L \le R \le 10^{18}$
• $0 \le D \le 10^{18}$
• $0 \le K \le 10^{18}$

输入格式

The first line contains three integers $B$, $A$ and $T$ — the base, the reference integer, and the number of queries.

Each of the next $T$ lines contains four integers $D, L, R, K$ — the parameters of one query.

输出格式

Output $T$ lines. The $i$-th line contains a single integer — the answer to the $i$-th query.

样例输入 #1

10 25 4
0 1 30 2
5 1 30 2
5 1 30 1
1 1 20 0

样例输出 #1

9
0
5
0

样例输入 #2

10 9 3
0 1 8 0
1 1 8 1
0 1 8 1

样例输出 #2

0
7
8

提示

• $D = 0$ is allowed; then the second condition reduces to $h(x) = K$. - From $x + D \le R$ it follows that $x \le R - D$. When $R \lt D$ the range of valid $x$ is empty and the answer is $0$.
• All answers fit in a 64-bit signed integer. Use 64-bit integers throughout.