解题思路

本题要求统计区间 $[l,r]$ 中恰好为 $x$ 位数的整数个数。按照位数定义：

• $x=1$：位数区间为 $[1,9]$
• $x\ge 2$：位数区间为 $[10^{x-1},\,10^x-1]$

将“位数区间”和给定区间 $[l,r]$ 做区间交集，交集长度即为答案：

题目内容

笨蛋同学拿到了一个随机数据生成器，它会在区间 $[l,r]$ 上以等概率生成一个整数。她想知道：区间内恰好为 $x$ 位数的整数有多少个。

请你输出在 $[l,r]$ 中，恰好是 $x$ 位数的整数个数。

在本题中，$x$ 位数定义为：当 $x = 1$ 时，为区间 $[1,9]$ 内的整数；当 $x ≥ 2$ 时，为区间 $[10^(x-1), 10^x - 1]$ 内的整数。

输入描述

第一行输入两个整数 $l,r (1 ≤ l ≤ r ≤ 2 × 10^9)$，表示生成器的取值范围。

第二行输入一个整数 $q (1 ≤ q ≤ 9)$，表示询问的次数。

此后 $q$ 行，第 $i$ 行输入一个整数 $x_i (1 ≤ x_i ≤ 9)$，表示第 $i$ 次询问的位数。

输出描述

输出 $q$ 行。对于每次询问，输出一个整数，表示在区间 $[l,r]$ 中恰好为 $x$ 位数的整数个数。

样例1

输入

1 20
4
1
2
3
9

输出

9
11
0
0

说明

区间 $[1,20]$ 中，$1$ 位数共有 $9$ 个 $(1$ ~ $9)$，$2$ 位数共有 $11$ 个 $(10$ ~ $20)$，更高位不存在。