Bajtazar has undertaken the task of editing $n$ films containing solutions to problems from the Olympiad in Informatics. It is known that editing the $i$-th film will take $t_i$ consecutive days, and it must be published by the end of the $d_i$-th day. Bajtazar has access to a fiber-optic connection, so once a film is edited, it is published on the Olympiad server almost immediately. However, the editing process is very hardware-intensive, and Bajtazar has only one computer, so only one film can be edited at a time.

There are many films, and Bajtazar is worried that he will not meet all the deadlines. Help him determine the maximum number of films Bajtazar can publish on time, assuming that the first editing session can start no earlier than day 1. To help Bajtazar feel more confident, also plan how to achieve this result.

Input

The first line of the input contains an integer $n$ ($1 \le n \le 500\,000$) representing the number of films to be edited.

The next $n$ lines contain descriptions of the films; the $i$-th of these lines contains two integers $t_i$ and $d_i$ ($1 \le t_i, d_i \le 10^9$) representing the editing time and the publication deadline for the $i$-th film.

Output

Your program should output, on the first line, a single integer $m$ representing the maximum number of films that Bajtazar can edit on time.

In the next $m$ lines, you should write the work plan; in the $i$-th of these lines, you should output two integers $f_i$ and $k_i$ ($1 \le f_i \le n, 1 \le k_i$), indicating that the film with index $f_i$ should start being edited on day $k_i$.

If there is more than one solution with the maximum $m$, your program may output any of them.

Examples

Input 1

5
4 5
2 4
5 3
1 9
3 10

Output 1

3
2 3
4 7
5 8

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups. If your program correctly outputs the first line of the output (the number $m$), but the remaining lines are incorrect, it will receive 50% of the points assigned to the test.