После вчерашнего младшего тура Елена Владимировна очень разозлилась на детей, так как они не набирали баллы по задачам. Сегодня она решила покончить с этим раз и навсегда.

Она села на самолет из Сочи в Москву и приехала в ЛОШ, где увидела \(n\) детей, у которых были нули по задачам. Каждый школьник обладает "гнилью", которую Елена Владимировна характеризует натуральным числом. "Гниль" \(i\)-ого школьника, она оценивает как \(s_i\).

Чтобы избавить общество от "гнили", она решает учить детей, но этот процесс ухудшает ее настроение. После отдыха в Сириусе ее настроение оценивается натуральным числом \(x\), при этом, обучив \(i\)-ого школьника, оно становится равным \(x=\lfloor \frac{x}{s_i} \rfloor\). Когда настроение уменьшится до 0, она перестает учить школьников и возвращается в Сочи.

Младшие преподаватели заботятся о настроении Елены Владимировны, поэтому со временем они заставляют некоторых школьников с подряд идущими номерами сдавать задачи, после чего их "гниль" уменьшается на 1 с каждой решенной задачей, но она не может стать меньше 1. Другими словами, иногда Вы узнаете, что школьники на отрезке [\(l\), \(r\)] решили новую задачу, и для \(i \in \) [\(l\), \(r\)] гниль" \(i\)-ого школьника стала равной \(s_i = \max(s_i - 1, 1)\).

Елена Владимировна разрабатывает стратегии обучения школьников. Каждая стратегия характеризуется 3 числами \(l\), \(r\) и \(x\): она будет по очереди обучать детей с номерами \(l\), \(l+1\), \(\dots\), \(r\) , при этом ее начальное настроение равно \(x\).

Помогите Елене Владимировне, выведите номер ребенка, после обучения которого, ее настроение уменьшится до \(0\). Если Елена Владимировна обучит всех детей и ее здоровье останется большим \(0\)  — выведите «-1» (без кавычек).