题目描述

小时候的雨荨非常听话，是父母眼中的好孩子。在学校是老师的左右手，同学的好榜样。后来她成为艾利斯顿第二代考神，这和小时候培养的良好素质是分不开的。雨荨的妈妈也为有这么一个懂事的女儿感到高兴。

一次期末考试，雨荨不知道第多少次，再次考了全年级第一名。雨荨的妈妈看到女儿 100 分的成绩单时，脸上又泛起了幸福的笑容，作为奖励，她给雨荨买了 $n$ 个布娃娃。

细心的雨荨发现，第 $i$ 个布娃娃有一个耐心值 $p_i$ 以及一个魅力值 $c_i$，并且还有能够忍受的耐心值的上限 $r_i$ 以及下限 $l_i$。当一个布娃娃 $j$ 满足 $l_j\leq p_i$ 并且 $p_i\leq r_j$，那么布娃娃 $j$ 喜欢布娃娃 $i$。雨荨还发现，一个布娃娃有可能喜欢它自己。

每个布娃娃心中都有一个谜团，具体来说就是：第 $i$ 个布娃娃想知道喜欢它的布娃娃中，魅力值第 $i$ 大的布娃娃的魅力值是多少，并且称这个布娃娃的谜团答案为这个魅力值的大小，如果不存在，那么这个布娃娃的谜团答案为 $0$。

鉴于雨荨的上司栋栋不让题目的数据过大，下面给出数据的生成方法：给出 $16$ 个参数：

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

$p_1=\text{Pfirst}\bmod\; \text{Pmod}$，$p_i=(p_{i-1}\times \text{Pprod}+\text{Padd}+i)\bmod\; \text{Pmod}(i>1)$。

对于 $c,l,r$ 数组也有类似的得到方式,，注意：$l$ 和 $r$ 数组生成完之后，如果某个布娃娃的忍耐度上 限小于下限，那么交换它的上限和下限。

当然，雨荨也不会让你告诉她每个布娃娃的谜团答案，因为那样会使输出数据很大。所以雨荨希望你告诉她，所有布娃娃谜团答案的和除以 $19921228$ 的余数是多少。

输入格式

输入的第一行有一个整数 $n$，代表布娃娃的个数。 输入的第二行有 $16$ 个用空格隔开的整数，分别代表：

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

输出格式

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

样例输入

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

样例输出

4

数据规模与约定

对于 $100\%$ 的数据，输入中的所有数均在 $[1,10^8]$ 范围内，$n\leq 1\times 10^5$。