题目内容

小蓝正在研究一种数字信号处理技术。现有一个长度为 $n$ 的信号序列 $S_1, S_2, \dots, S_n$，每一个信号的值都是 $0$ 到 $9$ 之间的整数。

小蓝发明了一种称为“倍频转置器”的工具，可以设定一个转置因子 $t$。对某段连续的信号使用转置器后，原来值为 $x$ 的信号会变成 $(x \times t) \bmod 10$，即只保留乘积的个位数。

现在一共有 $q$ 次询问，每次询问由三个参数 $l, r, t$ 给出，表示对区间 $[l, r]$ 内的所有信号使用转置因子 $t$。对于每个询问，你需要输出 $10$ 个整数，分别表示变换后值为 $0, 1, \dots, 9$ 的信号各出现了多少次。

约束条件：信号序列长度 $n$ 不超过 $10^5$。每个元素均为 $0$ 到 $9$ 的整数。询问次数 $q$ 不超过 $10^5$。每次询问满足 $1 \le l \le r \le n$，且 $1 \le t \le 10^5$。

输入描述

第一行输入一个整数 $n$ ($1 \le n \le 10^5$)，表示信号序列的长度。 第二行输入 $n$ 个整数 $S_1, S_2, \dots, S_n$ ($0 \le S_i \le 9$)，表示信号序列。 第三行输入一个整数 $q$ ($1 \le q \le 10^5$)，表示询问的数量。 接下来 $q$ 行，每行输入三个整数 $l, r, t$ ($1 \le l \le r \le n$，$1 \le t \le 10^5$)，表示一次询问。

输出描述

对于每一次询问，在一行上输出 $10$ 个用空格分隔的整数，依次表示变换后值为 $0, 1, \dots, 9$ 的信号个数。

样例1

输入

4
3 7 1 9
2
1 3 2
2 4 5

输出

0 0 1 0 1 0 1 0 0 0
0 0 0 0 0 3 0 0 0 0

说明

第一次询问 $l=1, r=3, t=2$，$t \bmod 10 = 2$。区间内数字为 3,7,1，每个出现一次。映射：$3 \times 2 \bmod 10 = 6$，$7 \times 2 \bmod 10 = 4$，$1 \times 2 \bmod 10 = 2$。因此结果中 2、4、6 各出现 1 次，其余数字 0 次。

第二次询问 $l=2, r=4, t=5$，$t \bmod 10 = 5$。区间内数字 7,1,9 各出现一次。映射：$7 \times 5 \bmod 10 = 5$，$1 \times 5 \bmod 10 = 5$，$9 \times 5 \bmod 10 = 5$。三个数字均变为 5，所以 5 出现 3 次。

样例2

输入

5
0 8 5 2 5
2
1 2 10
3 5 20

输出

2 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0

说明

第一次询问 $l=1, r=2, t=10$，$t \bmod 10 = 0$。区间内数字为 0,8，分别出现 1 次。映射 $d \times 0 \bmod 10 = 0$，因此所有数字都变成 0，0 共出现 2 次。

第二次询问 $l=3, r=5, t=20$，$t \bmod 10 = 0$。区间 5,2,5 共三个数字全部映射到 0，输出 0 出现 3 次。此样例体现了转置因子个位为 0 时的边界情况。

样例3

输入

6
2 4 6 8 0 2
1
1 6 13

输出

1 0 1 0 1 0 2 0 1 0

说明

询问 $l=1, r=6, t=13$，$t \bmod 10 = 3$。原始序列为 2,4,6,8,0,2。各数字出现次数：0 出现 1 次，2 出现 2 次，4 出现 1 次，6 出现 1 次，8 出现 1 次。

映射表（$d \times 3 \bmod 10$）：$2 \rightarrow 6$，$4 \rightarrow 2$，$6 \rightarrow 8$，$8 \rightarrow 4$，$0 \rightarrow 0$。累计后 0 出现 1 次，2 出现 1 次，4 出现 1 次，6 出现 2 次，8 出现 1 次，其余为 0。