题目描述

很久很久以前，中原地区分成了 $N$ 个国家，编号为 $1\sim N$，任意两个国家都可互达。每个国家有一个攻击值 $A_i$ 和防御值 $B_i$ 。定义一个人从 $i$ 国去 $j$ 国的危险值为：假如 $A_i>B_j$ ，则危险值为 $A_i^2-B_j^2$，否则危险值为 $0$ 。现在，Nan 从国家 $1$ 出发，经过每一个国家有且仅有一次，最后回到国家 $1$ ，要求找出一种方案，使得其中危险值的最大值最小。

输入格式

第一行正整数 $N$ ，表示有 $N$ 个国家；

第二行正整数 $A_1,A_2,x,y,z$，有等式 $A_i=(x\times A_{i-1}+y\times A_{i-2}+z)\mod 32767$；

第三行正整数 $B_1,B_2,x,y,z$，有等式 $B_i=(x\times B_{i-1}+y\times B_{i-2}+z)\mod 32767$。

输出格式

输出一个数,表示危险值的最大值最小是多少。

5
2 4 1231 4432 123
123 45 3245 555 6676

9171832

数据规模与约定

对于 $100\%$ 的数据， $1\le N\le 10^6$

样例说明

A 数组为 $2,4,13911,5151,3031$ 。 B 数据为 $123,45,24364,26060,21765$。 其中一种最优方案为 $1- 2- 4- 3- 5-1$，危险值分别为 $0,0,0,0,9171832$。