K 先生正在设计一个由 $N$ 行 $N$ 列组成的网格图案。为了实现这一目标，他决定用整数表示的颜色来涂满每个格子。我们将第 $i$ 行（$1 \le i \le N$）第 $j$ 列（$1 \le j \le N$）的格子称为格子 $(i, j)$。

目前，第一列和第一行的格子已经涂好了颜色。具体来说，格子 $(i, 1)$（$1 \le i \le N$）被涂上了颜色 $A_i$，格子 $(1, j)$（$1 \le j \le N$）被涂上了颜色 $B_j$。注意 $A_1 = B_1$。

对于剩余未涂色的格子，K 先生将按照以下步骤进行涂色：

• 对于每个 $i = 2, 3, \dots, N$，按顺序对第 $i$ 行的格子进行涂色：
  • 对于每个 $j = 2, 3, \dots, N$，按顺序将格子 $(i, j)$ 涂上以下两种颜色中数值较大的一种：
    • 格子 $(i - 1, j)$ 的颜色，以及
    • 格子 $(i, j - 1)$ 的颜色。 如果两种颜色数值相同，则涂上该颜色。

K 先生希望确定在所有 $N^2$ 个格子都被涂色后，出现次数最多的颜色，以及该颜色被涂在多少个格子上。

请编写一个程序，给定网格的大小以及第一列和第一行的颜色信息，确定出现次数最多的颜色编号以及该颜色被涂在的格子数量。如果多种颜色出现的次数相同且均为最多，则输出其中最大的颜色编号。

输入格式

从标准输入读取以下数据：

$N$ $A_1 \ A_2 \ \dots \ A_N$ $B_1 \ B_2 \ \dots \ B_N$

输出格式

向标准输出打印一行，包含两个由空格分隔的整数：

1. 出现次数最多的颜色编号，以及
2. 该颜色被涂在的格子数量。

如果多种颜色出现的次数相同且均为最多，则输出其中最大的颜色编号。

数据范围

• $2 \le N \le 200\,000$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• $1 \le B_j \le 10^9$ ($1 \le j \le N$)
• $A_1 = B_1$
• 给定值均为整数。

子任务

1. (15 分) $N \le 500$, $A_i \le 100\,000$ ($1 \le i \le N$), $B_j \le 100\,000$ ($1 \le j \le N$)。
2. (10 分) $N \le 500$。
3. (20 分) $A_i \le 2$ ($1 \le i \le N$), $B_j \le 2$ ($1 \le j \le N$)。
4. (25 分) $A_i < A_{i+1}$ ($1 \le i \le N - 1$), $B_j < B_{j+1}$ ($1 \le j \le N - 1$)。
5. (30 分) 无附加限制。

样例

样例输入 1

3
5 2 5
5 3 1

样例输出 1

5 4

说明 1

在此样例中，网格中每个格子的颜色如下：

5 3 1 2 3 3 5 5 5

出现次数最多的颜色是 5，共出现在 4 个格子上。因此，按顺序打印 5 和 4，中间用空格分隔。

样例输入 2

3
1 7 8
1 3 5

样例输出 2

8 3

说明 2

在此样例中，网格中每个格子的颜色如下：

1 3 5 7 7 7 8 8 8

出现次数最多的颜色是 7 和 8，每种颜色各出现在 3 个格子上。在这种情况下，输出较大的颜色编号 8，以及格子数量 3，中间用空格分隔。

样例输入 3

4
2 1 2 1
2 1 1 2

样例输出 3

2 10