题目描述

一个数字的数字根定义为：这个数字每一位的数字加起来求和，反复这个过程直到和小于 $10$。例如 $64357$ 的数字跟为 $7$，因为 $6+4+3+5+7=25$，$2+5=7$。一个区间的数字根定义为这个区间所有数字和的数字根。

给定一个序列 $A_1,A_2,A_3,…,A_n$，你需要回答一些询问。每一个询问给定个区间 $[L,R]$，求出这个区间所有连续子区间里最大的前 $5$ 个不同的数字根，不够 $5$ 个的用 -1 补全。

输入格式

第一行一个整数 $N$，表示序列的长度。

第二行是 $N$ 个整数 $A_i(0≤A_i<10^9)$。

第三行是一个整数 $Q$ 表示询问次数。

接下来 $Q$ 行，每一行两个正整数 $l,r$，表示询问区间。（$1≤l≤r≤N$）

输出格式

$Q$ 行，表示每一个查询区间所有连续子区间里最大的前 $5$ 个不同的数字根，按降序输出，输出用空格隔开。

5
101 240 331 4 52
3
1 3
4 5
1 5

8 7 6 4 2
7 4 2 -1 -1
9 8 7 6 4

第一个查询区间 $[1,3]$，它的连续子区间有 $[1,1],[2,2],[3,3],[1,2],[2,3],[1,3]$。可对应的数字根分别为 $2,6,7,8,4,6$。所以最大的 $5$ 个是 $8,7,6,4,2$。

提示

$30\%$ 的数据，$N, Q ≤ 1000$。

$100\%$ 的数据，$N, Q ≤ 100000$。