У вас есть массив \(a\), состоящий из \(n\) нулей. Также, вам дан набор из \(m\) необязательно различных отрезков. Каждый отрезок задается двумя числами \(l_i\) и \(r_i\) (\(1 \le l_i \le r_i \le n\)) и представляет собой подмассив \(a_{l_i}, a_{l_i+1}, \dots, a_{r_i}\) массива \(a\).
Назовём отрезок \(l_i, r_i\) красивым, если количество единиц на этом отрезке строго больше, чем количество нулей. Например, если \(a = [1, 0, 1, 0, 1]\), тогда отрезок \([1, 5]\) является красивым (количество единиц равно \(3\), количество нулей равно \(2\)), но отрезок \([3, 4]\) не является красивым (количество единиц равно \(1\), количество нулей равно \(1\)).
У вас также есть \(q\) изменений. Каждое изменение задано числом \(1 \le x \le n\), это означает, что вы должны присвоить элементу \(a_x\) значение \(1\).
Вы должны найти первое изменение, после которого хотя бы один из \(m\) заданных отрезков становится красивым, или сообщить, что ни один из них не является красивым после применения всех \(q\) изменений.
Выходные данные
Для каждого набора входных данных выведите одно целое число — наименьший номер изменения, после которого хотя бы один из отрезков окажется красивым, или \(-1\), если ни один отрезок не станет красивым.
Примечание
В первом примере, после первых двух изменений не будет красивых отрезков, а после третьего изменения на отрезке \([1; 5]\) будет 3 единицы и 2 нуля, получается ответ 3.
Во втором примере у нас не будет красивых отрезков.