为了给 CCO 做出贡献，Robert 试图发明一道线段树题目。该题目的具体要求如下：

给定一个包含 $N$ 个不同整数的列表，这些整数在 $1$ 到 $N$ 之间。它们按行排列，使得从左侧起第 $i$ 个整数为 $a_i$，其中 $1 \le i \le N$。我们定义集合上的“翻转”（flop）操作为交换该集合中的最小值与最大值。将会有 $Q$ 次翻转操作，每次操作指定两个数字 $l$ 和 $r$（$1 \le l \le r \le N$）。对于每次操作，你必须在区间 $[l, r]$ 上执行一次翻转（即在数字序列 $a_l, a_{l+1}, \dots, a_{r-1}, a_r$ 上进行）。你必须按给定的顺序执行这 $Q$ 次翻转，并报告最终结果。

现在他已经完成了题目描述，Robert 需要创建一些测试数据。特别是在一个测试用例中，他试图将一个内部笑话编码到初始序列和最终序列中。在固定这两个序列的情况下，请帮助他找到任何能够将第一个序列转换为第二个序列的翻转操作序列。

输入格式

第一行包含整数 $N$（$1 \le N \le 4096$）。第二行包含 $N$ 个不同的、由空格分隔的 $1$ 到 $N$ 之间的整数，表示初始序列。第三行也包含 $N$ 个不同的、由空格分隔的 $1$ 到 $N$ 之间的整数，表示最终序列。

输出格式

输出的第一行应包含整数 $Q$，其中 $Q \le 300\,000$。接下来的 $Q$ 行应包含两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le N$。

在总共 25 分中，有 5 分满足 $N \le 100$。 另外有 10 分满足 $N \le 2048$。

样例

输入 1

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

输出 1

4
2 3
3 6
2 5
4 5

说明 1

第一次翻转交换了 3 和 5，第二次翻转交换了 6 和 2，第三次翻转交换了 5 和 2，第四次翻转交换了 5 和 4。