Exchange

Initially, all natural numbers are arranged in a list in their standard order. You are allowed to perform the following operation: swap(a, b). This operation calculates the distance between the numbers a and b in the current list and then swaps their positions.

You are given a sequence of swap operations. Your task is to output the result of each operation to the output file.

Input

The first line of the input file contains the integer n (1 ≤ n ≤ 200000), which represents the number of operations. Each of the next n lines contains two integers, each ranging from 1 to 10^9, which are the arguments for the swap operations.

Output

For each operation provided in the input file, output the result of the operation.

Examples