Поняв, что управляющая зоопарком — это всего лишь утка, животные свергли ее. Теперь им предстоит решить между собой вопрос о новом правителе в ходе боевого турнира следующего формата:
Изначально животное \(0\) — это король, в то время как все остальные выстраиваются в очередь, с животным \(1\) в начале очереди и животным \(n-1\) в конце. Животное в начале очереди бросает королю вызов на поединок, и животное с большей силой выигрывает поединок. Победитель становится королем, а проигравший станет в конец очереди.
Животное, которое выигрывает \(3\) поединка подряд будет короновано правителем всего зоопарка. Сила каждого животного зависит от того, сколько последовательных поединков оно выиграло. Животное \(i\) имеет силу \(A_i\) с \(0\) выигрышами подряд, \(B_i\) с \(1\) выигрышем подряд и \(C_i\) с \(2\) выигрышами подряд. Изначально у каждого животного \(0\) выигрышей подряд.
Для всех животных, \(A_i > B_i\) и \(C_i > B_i\). Также все значения \(A_i\), \(B_i\), \(C_i\) попарно различны (все \(3n\) значений попарно различны).
Другими словами, животное, не являющееся королем, имеет силу \(A_i\). Король обычно имеет силу \(B_i\) или \(C_i\). Исключение составляет первый ход, первый король (животное \(0\)) имеет силу \(A_i\).
Кто станет новым правителем, и после скольких поединков? Или животные будут сражаться вечно, и никто не станет правителем?
Выходные данные
Выведите два целых числа в одной строке. Первое — это номер животного, ставшего правителем, а второе — количество прошедших поединков, пока какое-либо животное не станет правителем.
Если животные будут драться бесконечно долго, выведите -1 -1.
Примечание
Ниже описана последовательность событий для второго примера. Обратите внимание, что в бою \(1\) король (животное \(0\)) имеет силу \(A_0\). Турнир заканчивается на поединке \(7\), как животное \(1\) выигрывает поединок \(5\), \(6\) и \(7\). 