Ants

Interview

Time limit2sMemory limit128 MB

Summary

Simulate ants that reverse on collision by treating collisions as pass-throughs, then track identities to find which numbered ant falls off last and when.

Level: Medium5 of 10
Topics: Simulation, Math, Greedy
Solved: No attempts yet

Problem

N ants stand at distinct positions on a rod of length L. Treat each ant as a point with no size. Each position is an x-coordinate strictly between 0 and L.

Each ant is moving either left or right, and every ant moves at the same speed: 1 unit per second. When two ants meet, both immediately reverse direction and continue moving.

When an ant reaches position 0 or position L, it falls off the rod. Given the initial state of every ant, find the number of the ant that falls last and the time when it falls.

Input

The first line contains two integers N and L.

Each of the next N lines gives one ant's initial state in input order. If the value is positive, the value is the ant's position and the ant is moving to the right. If the value is negative, its absolute value is the ant's position and the ant is moving to the left.

The constraints are:

1 <= N <= 100000
2 <= L <= 1000000000
All ant positions are distinct.
Every position is greater than 0 and less than L.

Output

Print two integers i and t on one line.

i is the number of the ant that falls last. Ants are numbered from 1 to N in input order. t is the time when that ant falls.

Inputs where more than one ant falls last at the same time are not given.

Examples2

Example 1
Input
```
2 5
4
-3
```
Expected output
```
2 3
```
Example 2
Input
```
1 10
3
```
Expected output
```
1 7
```