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

题目描述

小时候的雨荨非常听话，是父母眼中的好孩子。在学校是老师的左右手，同学的好榜样。

后来她成为艾利斯顿第二代考神，这和小时候培养的良好素质是分不开的。

雨荨的妈妈也为有这么一个懂事的女儿感到高兴。

一次期末考试，雨荨不知道第多少次，再次考了全年级第一名。

雨荨的妈妈看到女儿$\red {100}$分的成绩单时，脸上又泛起了幸福的笑容，作为奖励，她给雨荨买了$\red n$个布娃娃。

细心的雨荨发现，第$\red i$个布娃娃有一个耐心值$\red {P[i]}$以及一个魅力值$\red {C[i]}$，

并且还有能够忍受的耐心值的上限$\red{R[i]}$以及下限$\red{L[i]}$。

当一个布娃娃$\red{j}$满足$\red{L[j]<=P[i]}$并且$\red{P[i]<=R[j]}$，那么布娃娃$\red j$喜欢布娃娃$\red i$。

雨荨还发现，一个布娃娃有可能喜欢它自己。

每个布娃娃心中都有一个谜团，具体来说就是：第$\red i$个布娃娃想知道喜欢它的布娃娃中，魅力值第$\red i$大的布娃娃的魅力值是多少，并且称这个布娃娃的谜团答案为这个魅力值的大小，如果不存在，那么这个布娃娃的谜团答案为$\red 0$。鉴于雨荨的上司栋栋不让题目的数据过大，下面给出数据的生成方法：给出$\red{16}$个参数：

Padd, Pfirst, Pmod, Pprod, Cadd, Cfirst, Cmod, Cprod, Ladd, Lfirst, Lmod, Lprod, Radd, Rfirst, Rmod, Rprod。

---

$\red{P[1]}$ = Pfirst $\red \%$ Pmod, $\red{P[i]}$ = ($\red{P[i-1]}$ Pprod + Padd + $\red{i}$) $\red{\%}$ Pmod ($\red{i > 1}$)。

---

对于$\red{C、L、R}$数组也有类似的得到方式, $\red{\%}$代表取余运算。

注意：$\red{L}$和$\red{R}$数组生成完之后，如果某个布娃娃的忍耐度上限小于下限，那么交换它的上限和下限。

当然，雨荨也不会让你告诉她每个布娃娃的谜团答案，因为那样会使输出

数据很大。所以雨荨希望你告诉她，所有布娃娃谜团答案的和除以$\red{19921228}$的余数是多少。

输入格式

输入的第一行有一个整数$\red n$，代表布娃娃的个数。

输入的第二行有$\red{16}$个用空格隔开的整数

分别代表Padd,Pfirst,Pmod,Pprod,Cadd,Cfirst,Cmod,Cprod,Ladd,Lfirst,Lmod,Lprod,Radd,Rfirst,Rmod,Rprod。

$\red{16}$个参数均为$\red{ 1 \sim 10^8}$中的整数。

输出格式

输出一个整数，代表所有布娃娃谜团答案的和除以19921228的余数。

样例

样例输入

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

样例输出

4