解题思路

先注意到题目里真正起作用的是$k \bmod 10$，因为观察到的值为：

$A[i] \times k \bmod 10$

而$A[i] \in [0,9]$，所以只和$k$的个位有关。

对于一个询问$(l,r,k)$，如果我们知道区间$[l,r]$中原始数字$0\sim 9$各出现了多少次，那么设原数字$x$在区间内出现次数为$cnt[x]$，放大后它会全部变成：

题目内容

给出一个长度为$n$的整数数组$A1,A2,A3,…,An$,其中$0≤A[i]≤9$.

小红有一个神奇的数字放大镜，可以设置放大倍数为$k$,然后用这个放大镜观察区间$[l,r]$的数，对于第$i(l≤i≤r)$个数$Ai$在放大镜下观察到的值为$A[i]×kmod10$,既只观察到放大后的个位。

现在，一共有$q$次询问，第$i$次询问用一个三元组$(l_i,r_i,k_i)$表示，表示用放大倍数为$k_i$的放大镜在区间$[l_i,r_i]$观察，对于每个询问，输出$10$个整数，分别表示观察到的$A[i]$的值为$0$~$9$的个数。

输入描述

第一行输入一个整数$n(1≤n≤10^5)$代表数组中的元素数量。

第二行输入$n$个整数$A1,A2,A3,…,An(0≤A[i]≤9)$代表数组元素。

第三行输入一个整数$q(1≤q≤10^5)$表示询问的数量。

此后$q$行，每行输入三个数字$l_i,r_i,k_i(1≤l_i≤r_i≤n；1≤k_i≤10^5)$代表一次询问三元组。

输出描述

对于每一次间问，在一行上输出十个整数，分别表示观察到的$A[i]$的值为$0$~$9$的个数。

样例1

输入

5
1 2 3 4 5
2
1 3 6
2 5 8

输出

0 0 1 0 0 0 1 0 1 0
1 0 1 0 1 0 1 0 0 0

说明

对于第一次询问，观察的数初始为$1,2,3$，在放大$6$倍后，变为$6,2,8$。

对于第二次间问，观察的数初始为$2,3,4,5$，在放大$8$倍后，变为$6,4,2,0$。

样例2

输入

10
0 9 9 3 7 1 1 1 0 6
10
5 6 78237
1 3 23418
3 4 48605
8 9 11466
1 5 42119
5 8 80036
1 5 49470
1 4 22896
5 8 91573
2 5 57175

输出

0 0 0 0 0 0 0 1 0 1 
1 0 2 0 0 0 0 0 0 0 
0 0 0 0 0 2 0 0 0 0 
1 0 0 0 0 0 1 0 0 0 
1 2 0 1 0 0 0 1 0 0 
0 0 1 0 0 0 3 0 0 0 
5 0 0 0 0 0 0 0 0 0 
1 0 0 0 2 0 0 0 1 0 
0 1 0 3 0 0 0 0 0 0 
0 0 0 0 0 4 0 0 0 0

说明