Aroma Ring Snapshot

Time limit: 2000 msMemory limit: 256 MB

An artisan keeps $N$ vials on a circular shelf, in positions $1, 2, \ldots, N$ clockwise. After position $N$ comes position $1$ again. The vial at position $i$ has quantity $V_i$ and aroma code $A_i$ .

A snapshot is described by a starting position $L$ and a length $C$ , where $1 \le L \le N$ and $1 \le C \le N$ . It contains the distinct positions reached by starting at and moving clockwise. More precisely, its -th position is

P_j = ((L + j - 2) \bmod N) + 1

for $1 \le j \le C$ .

The snapshot has total quantity

Q = \sum_{j=1}^{C} V_{P_j}

and aroma span

S = \max_{1 \le j \le C} A_{P_j} - \min_{1 \le j \le C} A_{P_j}.

A snapshot is successful if $Q \ge X$ and $S \le K$ .

Choose a successful snapshot with the smallest possible length $C$ . If several successful snapshots have this same smallest $C$ , choose the one with the smallest starting position $L$ .

Input

The first line contains three integers $N$ , $X$ , and $K$ ( $1 \le N \le 2 \times 10^5$ , , ), the number of vials, the required total quantity, and the maximum allowed aroma span. The next lines describe the vials in order from position to position . The -th of these lines contains two integers and (, ), the quantity and aroma code of the vial at position . All integers on the same line are separated by spaces.

Output

If no successful snapshot exists, print one line containing the single integer $-1$ . Otherwise, print one line containing three integers $C$ , $L$ , and $R$ , separated by spaces. Here $C$ is the chosen length, $L$ is the chosen starting position, and is the ending position:

Samples

Sample 1

Input

Output

2 2 3

The output selects the snapshot containing positions $2$ and $3$ . Its total quantity is $8$ and its aroma span is $2$ .

Sample 2

Input

Output

2 4 1

The output selects positions $4$ and $1$ , in that order. The snapshot wraps around the shelf, has total quantity , and has aroma span .

Aroma Ring Snapshot

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions

Sample 3