You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

本题的“陈”可以指代多个人。

题目描述

陈和她的日子就这样结束了。

陈非常不舍，因此回忆起过去和她的点点滴滴。

他回忆起每一天和她的日子，并将这一天对他的满意度定为 $x$。与她相处的日子，让他学会了从他人角度出发看待事情，因此，他也会试图理解她，定下她对他的满意度 $y$。那么，这一天的满意度一定是在 $[\min\{x,y\},\max\{x,y\}]$ 这个区间内。

陈想知道可能最长的一段连续的日子，这些日子的满意度是随着时间单调不减的。那是令人难忘的。

他同时也想知道可能最长的一段连续的日子，这些日子的满意度是单调不升的。那是引以为戒的。

输入格式

第一行一个正整数 $n$，表示相处的日子数。

接下来 $n$ 行，每一行两个正整数 $l_i,r_i$。对于整个输入数据的第 $i+1$ 行，表示第 $i$ 天的满意度为 $[\min\{l_i,r_i\},\max\{l_i,r_i\}]$。

输出格式

两行，第一行两个正整数 $p,q$，第二行两个正整数 $x,y$，分别表示可能最长的一段连续单调不减的日子 $[p,q]$ 和可能最长的一段连续单调不升的日子 $[x,y]$。

如果存在多个 $[p,q],[x,y]$ 符合要求，取 $p,x$ 更小的区间。

样例

7
1 4
2 5
3 4
-3 -1
7 8
4 5
1 4

1 3
1 4

数据范围

对于 $40\%$ 的数据，$1\le n\le 10^3,-100\le l_i, r_i\le 100$。

对于 $100\%$ 的数据，$1\le n\le 10^6,-10^8\le l_i, r_i\le 10^8,1\le p\le q\le n,1\le x\le y\le n$。

题外话

愿他，愿她，前途敞亮，美好回忆铭刻在心间，永远。