Slove Equations
题号：NC262428
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定 n 个模 998244353 意义下的函数，第 i 个函数为 f_i(x)=a_ix+b_i。

q 次询问，每次询问一个区间 [l,r] 以及一个整数 y，在模 998244353 意义下解如下方程 f_{l}\left(f_{l+1}\left(\ldots f_{r-1}\left(f_{r}(x)\right) \ldots\right)\right)\equiv y \pmod{998244353}，若有多个解 x 输出 inf，无解输出 -1。否则输出解 x。

输入描述:

第一行一个整数 n(1\leq n\leq 3\times 10^5)。

第二行 n 个非负整数，表示 a_i(0\leq a_i<998244353)。

第三行 n 个非负整数，表示 b_i(0\leq b_i<998244353)。

接下来一行一个整数 q(1\leq q\leq 3\times 10^5)。

接下来 q 行每行三个整数 l,r,y(1\leq l\leq r\leq n,0\leq y<998244353)。

输出描述:

接下来 q 行每行输出答案。若有多个解 x 输出 inf，无解输出 -1。否则输出解 x。
示例1

输入

复制 
3
1 5 2
5 8 2
4
1 2 0
2 3 9
1 3 7
1 1 5

输出

复制 
199648868
299473305
199648869
0