Мариан пришёл в казино. Игры в казино проходят следующим образом.
Перед каждым раундом игрок выбирает число от \(1\) до \(10^9\). После этого бросается игральная кость с \(10^9\) сторонами, и выпадает случайное число от \(1\) до \(10^9\). Если игрок угадал выпавшее число, количество его денег удваивается, в противном случае количество его денег уменьшается вдвое.
Мариан умеет предсказывать будущее, поэтому он знает все числа \(x_1, x_2, \dots, x_n\) которые выпадут на игральной кости в следующих \(n\) раундах.
Мариан хочет выбрать три числа \(a\), \(l\), \(r\) (\(l \leq r\)). Он будет играть \(r-l+1\) раунд (раунды с номерами от \(l\) до \(r\)). В каждом из этих раундов он будет загадывать одно и тоже число \(a\). На старте (перед раундом \(l\)) у него \(1\) доллар.
Мариан просит вас найти такие \(a\), \(l\) и \(r\) (\(1 \leq a \leq 10^9\), \(1 \leq l \leq r \leq n\)) таких, что в конце игры у него будет максимальная сумма денег.
Заметьте, что при проигрыше или выигрыше (т.е. уменьшении или увеличении количества денег вдвое) количество денег не округляется. Все операции деления/умножения проводятся с бесконечной точностью. Например, во время игры Мариан может иметь количество денег, равное \(\dfrac{1}{1024}\), \(\dfrac{1}{128}\), \(\dfrac{1}{2}\), \(1\), \(2\), \(4\), и т.д. (любое значение \(2^t\), где \(t\) — целое число любого знака).
Выходные данные
Для каждого набора выведите три числа — \(a\), \(l\), и \(r\) таких, что выигрыш Мариана в казино будет максимальным. Если существует несколько различных ответов, вы можете вывести любой из них.
Примечание
В первом наборе лучшим выбором будет \(a=4\), \(l=1\), \(r=5\). Игра пройдёт следующим образом:
- Мариан начинает игру с одним долларом.
- После первого раунда у Мариана будет \(2\) доллара, так как он угадал выпавшее число.
- После второго раунда у Мариана будет \(4\) доллара, так как он вновь угадал выпавшее число.
- После третьего раунда у Мариана будет \(2\) доллара, так как он загадал \(4\), а выпало число \(3\).
- После четвертого раунда у Мариана вновь будет \(4\) доллара.
- В последнем раунде Мариан закончит с \(8\) долларами, так как он вновь угадал выпавшее число.
Для второго набора есть много подходящих ответов, однако можно доказать что Мариан не может закончить играть с более чем \(2\) долларами, так что любой выбор \(l = r\) с подходящим \(a\) будет приемлемым.