题目背景

$$ \ \underline{0}\underline{5}\ \dot{\underline{5}}\dot{\underline{3}}\ {\LARGE|}\ \dot{2}\ \dot{\underline{2}}\dot{\underline{\underline{1}}}\overset{\frown}{\dot{\underline{\underline{2}}}\ \dot{\underline{2}}}\dot{\underline{3}}\ \underline{6}\dot{\underline{1}}\ {\LARGE|}\ \dot{\underline{2}}\dot{\underline{1}}\ \dot{\underline{2}}\dot{\underline{\underline{3}}}\dot{\underline{\underline{3}}}\ \underline{0}\underline{5}\ \dot{\underline{5}}\dot{\underline{3}}\ {\LARGE|}\ \dot{2}\ \dot{\underline{2}}\dot{\underline{\underline{1}}}\overset{\frown}{\dot{\underline{\underline{2}}}\ \dot{\underline{2}}}\dot{\underline{1}}\ \dot{\underline{2}}\dot{\underline{3}}\ {\LARGE|}\ \dot{\underline{2}}\dot{\underline{\underline{1}}}\overset{\frown\ }{\dot{\underline{\underline{1}}}\ \dot{1}\ } $$

$$ \ \underline{0}\underline{5}\ \dot{\underline{5}}\dot{\underline{3}}\ {\LARGE|}\ \dot{2}\ \dot{\underline{2}}\dot{\underline{\underline{1}}}\overset{\frown}{\dot{\underline{\underline{2}}}\ \dot{\underline{2}}}\dot{\underline{3}}\ \underline{6}\dot{\underline{1}}\ {\LARGE|}\ \dot{\underline{2}}\dot{\underline{1}}\ \dot{\underline{2}}\dot{\underline{\underline{3}}}\overset{\frown\ }{\dot{\underline{\underline{3}}}\ \dot{3}\ }\ \underline{0}\underline{5}\ {\LARGE|}\ \underline{6}\underline{.}\overset{\frown}{\dot{\underline{\underline{3}}}\ \dot{\underline{3}}}\underline{5}\ \underline{6}\underline{.}\overset{\frown}{\dot{\underline{\underline{2}}}\ \dot{\underline{2}}}\dot{\underline{2}}\ {\LARGE|}\ 6\ - $$

题目描述

鸽子大合唱分为四个声部。每个声部的旋律都是一个长为 $n$ 的序列，下标从 $1$ 开始。四个声部的旋律分别是 $a,b,c,d$。

由于合唱时间很长，鸽子们可能需要中途休息。在时间 $i$（$1\le i \le n-1$）休息的含义是：四个声部分别演唱至 $a_i,b_i,c_i,d_i$，然后休息，再从 $a_{i+1},b_{i+1},c_{i+1},d_{i+1}$ 开始演唱。

设休息时间为 $t_1,t_2,\dots, t_k$（$0\le k \le n-1$，$1\le t_1 < t_2 < \dots < t_k \le n-1$）。特别规定 $t_0=0,t_{k+1}=n$。为避免休息破坏合唱的连贯性，我们要求对任意 $1\le i\le k+1$，有

$$ \min_{j=t_{i-1}+1}^{t_i}a_j \le \min_{j=t_{i-1}+1}^{t_i}b_j \le \min_{j=t_{i-1}+1}^{t_i}c_j \le \max_{j=t_{i-1}+1}^{t_i}d_j $$

求： - 有几种可能的休息方案，对 $1914270647$ 取模； - 最多休息几次，即 $k$ 的最大值。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数，表示 $a_i$。

第三行 $n$ 个正整数，表示 $b_i$。

第四行 $n$ 个正整数，表示 $c_i$。

第五行 $n$ 个正整数，表示 $d_i$。

输出格式

第一行输出一个整数表示休息方案数对 $1914270647$ 取模的结果。

如果存在至少一个休息方案，在第二行输出一个整数表示最大休息次数。

样例一

input

3
3 2 2
1 2 2
3 3 1
3 3 3

output

0

样例二

input

9
8 4 3 8 6 8 6 1 4
9 4 5 8 6 6 7 9 2
5 9 8 7 8 4 8 8 8
1 7 3 5 7 3 4 8 6

output

9
2

样例三

见下发文件中的 $\text{ex_chorus3.in/ans}$，此样例满足测试点 $1\sim 2$ 的限制。

样例四

见下发文件中的 $\text{ex_chorus4.in/ans}$，此样例满足测试点 $5$ 的限制。

样例五

见下发文件中的 $\text{ex_chorus5.in/ans}$，此样例满足测试点 $8$ 的限制。

样例六

见下发文件中的 $\text{ex_chorus6.in/ans}$，此样例满足测试点 $11$ 的限制。

样例七

见下发文件中的 $\text{ex_chorus7.in/ans}$，此样例满足测试点 $14$ 的限制。

限制与约定

所有数据满足 $1\le n\le 10^6$，$1\le a_i,b_i,c_i,d_i \le n$。

特殊性质 A：保证 $a_i=b_i=1$。

特殊性质 B：保证 $c_i=d_i=n$。

特殊性质 C：保证 $d_i=n$。

特殊性质 D：保证 $a_i=1$。

本题部分测试点读入规模较大，建议采取效率较高的读入方式。