Problem Statement

You are given $N$ pairs of integers $(L_1, R_1), (L_2, R_2), \dots, (L_N, R_N)$. Here, $L_i \leq R_i$ for all $1 \leq i \leq N$.

A sequence of $N$ integers $A = (A_1, A_2, \ldots, A_N)$ is called a good integer sequence if it satisfies the following condition:

• $L_i \leq A_i \leq R_i$ for all $1 \leq i \leq N$.

Find the lexicographically smallest good integer sequence $A$ that minimizes $\displaystyle \sum_{i = 1}^{N-1} |A_{i+1} - A_{i}|$.

What is lexicographical order for sequences? A sequence $S = (S_1,S_2,\ldots,S_{|S|})$ is said to be lexicographically smaller than a sequence $T = (T_1,T_2,\ldots,T_{|T|})$ if 1. or 2. below holds. Here, $|S|, |T|$ denote the lengths of $S$ and $T$, respectively. $|S| \lt |T|$ and $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$. There is an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ such that both of the following hold: $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$. $S_i$ is smaller than $T_i$ (as a number).

Constraints

• All input values are integers.
• $2 \leq N \leq 5 \times 10^5$
• $0 \leq L_i \leq R_i \leq 10^9$

Input

The input is given from Standard Input in the following format:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

Output

Print the answer in a single line in the following format:

A_1 A_2 \ldots A_N