ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural FU Open Personal Contest 2014

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Snowboarding on Spilnaya

Time limit: 1.0 second
Memory limit: 64 MB
Winter in Yekaterinburg is the longest time of the year. And everyone spends long winter evenings in his own way. Kate regularly travels with her friends to the nearest ski resort — mountain Spilnaya — to go snowboarding. There is just opened a new track. But while Kate’s first ride on this track she felt deja vu, as if she has already ridden on exactly the same slope. Well, maybe a little sharper or flatter. She was so excited that instead of one more ride, she decided to check up, whether there were some sections of the slopes, where she was riding earlier, that were similar to the slope, which she has just moved out. Returning to her car and taking out the laptop, Kate found on the Internet detailed information on all the slopes she rode, including the new track on Spilnaya. This information corresponds to the map of heights in increments of one meter. Kate considers similar two sections of different slopes of the same length, if for the heights of the first section x0, x1, …, xn and for the heights of the second section y0, y1, …, yn and some numbers a and b, the equality xiyi = a · i + b is correct.

Input

The first line contains an integer n that is the number of slopes where Kate rode earlier (1 ≤ n ≤ 105). The second line contains an integer m, and integers x0xm, where m is the length of the slope, which Kate just moved out, and xi is the height above sea level of a point which is in the i metres from the start of the slope (1 ≤ m ≤ 105; −109xi ≤ 109). The next n lines describe all slopes, where Kate rode earlier. It is guaranteed that the sum of their lengths does not exceed 105.

Output

If there are such numbers i and j that the slope which Kate just moved out is similar to the section, starting with the j-th meter from the beginning of the i-th slope of those where she rode earlier, output numbers i and j separated with a space. The slopes are numbered with integers from 1 to n in the order in which they appear in the input data. If there are several matching pairs i and j, output the one with the minimal absolute value of a parameter of the similarity criterion. If there are still multiple solutions, output any of them. If these numbers do not exist, output −1.

Samples

inputoutput
2
2 3 2 1
5 21 15 10 6 3 2
4 10 7 5 3 2
2 1
3
2 0 0 0
1 0 0
2 1 2 4
1 5 17
-1
Problem Author: Dmitry Ivankov
Problem Source: Open Ural FU Personal Contest 2014
To submit the solution for this problem go to the Problem set: 2097. Snowboarding on Spilnaya