Сокровища

И вот что из меня вышло, Джим. А все оттого, что я смолоду ходил на кладбище играть в орлянку!

Бен Ганн

Будучи единственным человеком на острове, Бен Ганн тронулся умом. Он разделил сокровища в пещере на $n$ кучек и положил их в ряд. А теперь ему мерещится капитан Флинт, который хочет отобрать у него часть сокровищ.

Так как Флинт всего лишь галлюцинация, то его требования к своей части сокровищ необычны. Он хочет взять $k$ кучек, лежащих в ряду подряд, так, что бы суммарная стоимость сокровищ в этих кучках была не меньше, чем сумманая стоимость всех остальных сокровищ. Количество кучек при этом должно быть минимально возможным.

К сожалению, Бен Ганн не в состоянии сказать, какова стоимость каждой кучки. Единственное, что он помнит --- стоимости первых двух кучек, и то, что стоимость $i$-й кучки он вычислял по формуле $(a \cdot t\_{i-2} + b \cdot t\_{i-1} + c) \mod d$, где $a$, $b$, $c$ и $d$ --- константы, которые ему сообщил Ник Аллардайс, $t\_{i-1}$ и $t\_{i-2}$ --- стоимости $i-1$-й и $i-2$-й кучек соответственно.

Помогите Бену Ганну отдать часть своих сокровищ Флинту.

В первой строке входного файла задано число $n$ ($2 \le n \le 10^7$) --- количество кучек сокровищ. Во второй строчке находятся числа $x$ и $y$ ($0 \le x,y \le 10^9$) --- стоимости первых двух кучек. В третьей строчке находятся числа $a$, $b$, $c$ и $d$ ($0 \le a, b, c \le 10^9, 1 \le d \le 10^9$).

Выведите номера первой и последней кучек, которые необходимо взять Флинту. Если таких вариантов несколько, выведите любой.

Обратите внимание, что памяти в задаче мало.