D. 挣钱

你面前有 座城市，目前你手上有一些钱。在第 个城市，你可以做以下两件事情之一：

1、将你当前持有的钱的数目加上

2、将你当前持有的钱的数目乘以

现在会给你 次询问，第 次询问会给出三个数：、、。意思是：你最开始拥有 元，此时你进入了第 个城市，你将从第 个城市走到第 个城市，历经 、、... 、。在每一个历经的城市中，你都需要做上述两种事情之一来挣钱。对每次询问，求你最后最多能有多少钱，答案对 取模。

注意，你需要输出的是：最多的钱数对 取模的结果，而不是最大化“钱数模 ”。

题目来源：The 2024 Shanghai Collegiate Programming Contest，D 题

第一行输入正整数：

第二行输入以空格隔开的 个正整数：、、、...、

第三行输入以空格隔开的 个正整数：、、、...、

第四行输入正整数：

接着输入第 ~ 行，第 行有以空格隔开的三个整数，分别是 、、。

对每个询问，依次输出你的答案。以回车分隔，一行输出一个答案。

样例输入

5
3 4 5 2 5
1 1 9 6 3
2
1 1 4
5 4 5

样例输出

432
90