Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Nested Segments

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a sequence *a*_{1}, *a*_{2}, ..., *a*_{n} of one-dimensional segments numbered 1 through *n*. Your task is to find two distinct indices *i* and *j* such that segment *a*_{i} lies within segment *a*_{j}.

Segment [*l*_{1}, *r*_{1}] lies within segment [*l*_{2}, *r*_{2}] iff *l*_{1} ≥ *l*_{2} and *r*_{1} ≤ *r*_{2}.

Print indices *i* and *j*. If there are multiple answers, print any of them. If no answer exists, print -1 -1.

Input

The first line contains one integer *n* (1 ≤ *n* ≤ 3·10^{5}) — the number of segments.

Each of the next *n* lines contains two integers *l*_{i} and *r*_{i} (1 ≤ *l*_{i} ≤ *r*_{i} ≤ 10^{9}) — the *i*-th segment.

Output

Print two distinct indices *i* and *j* such that segment *a*_{i} lies within segment *a*_{j}. If there are multiple answers, print any of them. If no answer exists, print -1 -1.

Examples

Input

5

1 10

2 9

3 9

2 3

2 9

Output

2 1

Input

3

1 5

2 6

6 20

Output

-1 -1

Note

In the first example the following pairs are considered correct:

- (2, 1), (3, 1), (4, 1), (5, 1) — not even touching borders;
- (3, 2), (4, 2), (3, 5), (4, 5) — touch one border;
- (5, 2), (2, 5) — match exactly.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/09/2018 23:46:28 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|