Məsələlər
Отрезки на прямой возвращаются
Отрезки на прямой возвращаются
На прямой задано \textbf{N} попарно различных отрезков \[\textbf{a_i}, \textbf{b_i}\] (\textbf{i} = \textbf{1}, \textbf{2}, ..., \textbf{N}, \textbf{a_i} < \textbf{b_i}). Будем говорить, что отрезок номер \textbf{i} \textit{непосредственно содержится} в отрезке номер \textbf{j} (\textbf{i} ≠ \textbf{j}), если:
\begin{itemize}
\item он полностью принадлежит \textbf{j}-му (то есть \textbf{a_j} ≤ \textbf{a_i} и \textbf{b_i} ≤ \textbf{b_j});
\item среди заданных \textbf{N} отрезков не найдётся такого отрезка (с номером \textbf{k}), что \textbf{i}-й отрезок принадлежит \textbf{k}-му и \textbf{k}-й принадлежит \textbf{j}-му (здесь \textbf{i}, \textbf{j} и \textbf{k} - различные числа).
\end{itemize}
Ваша задача - для каждого из заданных отрезков найти тот, в котором он непосредственно содержится, либо сообщить, что таких нет. Если данный отрезок непосредственно содержится сразу в нескольких - подходит любой из них.
\InputFile
Сначала вводится целое число \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100000}). Далее идут \textbf{N} пар целых чисел \textbf{a_i}, \textbf{b_i} (\textbf{-10^9} ≤ \textbf{a_i} < \textbf{b_i} ≤ \textbf{10^9}).
\OutputFile
Выведите \textbf{N} чисел. Число номер \textbf{i} должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер \textbf{i}, либо \textbf{0} - если такого не существует.
Если существует несколько решений - выведите любое.
Giriş verilənləri #1
4 2 3 0 4 1 6 0 5
Çıxış verilənləri #1
3 4 0 0