C-小苯的波浪加密器_牛客周赛 Round 106

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯升级了她的数字波浪生成器，现在它变成了一个加密器。给定一个长度为 $n-2$ 的数字序列 $a_3,a_4,\dots,a_n$ 和两个区间 $[L_1, R_1]$ 、 $[L_2, R_2]$ 。
$\hspace{15pt}$ 数字波浪序列的生成过程如下：
$\hspace{23pt}\bullet\,$ 小苯从 $[L_1, R_1]$ 区间中选择一个数字作为波浪序列的第一个数字 $a_1$ 。
$\hspace{23pt}\bullet\,$ 小苯从 $[L_2, R_2]$ 区间中选择一个数字作为波浪序列的第二个数字 $a_2$ 。
$\hspace{23pt}\bullet\,$ 从第三个数字开始，每个数字都等于前面两个数字的乘积的个位数。
$\hspace{15pt}$ 现在小苯给定了你 $a_3$ 到 $a_n$ 的所有数字，请你还原出波浪序列对应的第一个和第二个数字 $a_1$ 和 $a_2$ 。如果存在多个解，请输出使得整个波浪序列字典序最小的答案（即优先最小化 $a_1$ ，其次最小化 $a_2$ ）。

$\hspace{15pt}$ 注意，输入只保证 $a_5$ 到 $a_n$ 满足上述关系； $a_3$ 、 $a_4$ 给出但不一定与未知的 $a_1$ 、 $a_2$ 一一对应，需求解时自行验证是否存在 $a_1$ 、 $a_2$ 使得整个序列一致。如果无解，则输出两个固定的整数 $-1$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入五个整数 。
第二行输入  个数字 ，保证对于任意的 ，有 。
除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行。如果不存在答案，在一行上输出两个固定的整数 ；否则，输出两个整数，表示你还原出来的能使整个波浪序列字典序最小的  和 。

示例1

输入

复制

2
4 2 100 5 100
4 6
5 1 1 1 1
4 6 4

输出

复制

6 9
-1 -1

说明

对于第一组测试数据，选择  是最优的，此时波浪序列为：，满足题目的要求，同时也是字典序最小的解。