该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

星幕显影（curtain）

题目描述

猪猪正在修复一段由 $n$ 帧影像组成的星幕记录。第 $i$ 帧影像的初始曝光等级为 $a_i$，将这一帧的曝光等级增加 $1$ 需要消耗 $c_i$ 的代价。

猪猪可以把第 $i$ 帧影像的曝光等级从 $a_i$ 提高到某个有理数 $x_i$，但不能降低，即必须满足 $x_i\ge a_i$。

每一帧影像还有一个最高安全曝光等级 $u_i$。若 $u_i=-1$，表示这一帧没有最高安全曝光限制；否则必须满足 $x_i\le u_i$。

曝光等级为 $x$ 的影像，其真实亮度记为 $2^x$。修复完成后，星幕记录需要满足如下校准规则：

对于任意三个整数 $l,i,r$，若 $1\le l<i<r\le n$，则第 $i$ 帧的真实亮度不能低于第 $l$ 帧与第 $r$ 帧按距离比例混合得到的参考亮度，即

修复总代价定义为

请你求出最小可能的修复总代价。若不存在满足要求的修复方案，输出 $-1$。

由于答案可能为有理数，若最小总代价为 $\dfrac{p}{q}$，你需要输出 $p\cdot q^{-1}\bmod 998244353$，其中 $q^{-1}$ 表示 $q$ 在模 $998244353$ 意义下的乘法逆元。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每一帧影像的初始曝光等级。

第三行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示每一帧影像的单位修复代价。

第四行包含 $n$ 个整数 $u_1,u_2,\ldots,u_n$，表示每一帧影像的最高安全曝光等级。若 $u_i=-1$，表示第 $i$ 帧没有最高安全曝光限制。

输出格式

若不存在满足要求的修复方案，输出一行一个整数 $-1$。

否则输出一行一个整数，表示最小修复总代价对 $998244353$ 取模后的结果。

样例

样例输入 #1

5
0 0 0 0 2
1 1 1 1 1
-1 -1 -1 -1 -1

样例输出 #1

3

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^5$，$0\le a_i\le 10^9$，$1\le c_i\le 10^9$，$u_i=-1$ 或 $a_i\le u_i\le 10^9$。

• 特殊性质 A：保证对所有 $1\le i\le n$，均有 $u_i=-1$。
• 特殊性质 B：保证对所有 $1\le i\le n$，均有 $c_i=1$ 且 $u_i=-1$。