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.

Time Limit: 1.0 s

Memory Limit: 128.0 MB

Little Ariya enjoys observing frogs in a pond. The pond has N lily pads arranged in a straight
line, numbered from 1 to N from left to right. Each lily pad i has a jump power denoted by ai,
which indicates how far a frog will jump when starting from that pad.

The behavior of a frog is as follows:

• When a frog starts on lily pad i, it jumps to lily pad i + ai.
• The frog continues jumping according to the jump power of the current lily pad.
• If a jump takes the frog to a position greater than N, the frog exits the pond.

Ariya wants to determine, for each lily pad, the number of jumps a frog would make before
exiting the pond and the last lily pad it visits before leaving.

Input

The first line contains an integer N (1 ≤ N ≤ 100,000) — the number of lily pads. The second
line contains N positive integers a₁, a₂, ..., aₙ (1 ≤ aᵢ ≤ N) — the jump powers of the lily pads.

Output

Output N lines. The i-th line should contain two space-separated integers:

1. The number of the last lily pad the frog visits before exiting the pond when starting from
   lily pad i.
2. The number of jumps the frog makes before exiting.

Sample

10
5 1 2 4 1 7 3 8 10 8

6 2
6 4
6 3
8 2
6 2
6 1
10 2
8 1
9 1
10 1