Mapping Update and Query

You are given a mapping \(f : [0, 2^{64})\to[0,2^{64})\) with an initial value \(f(x)=0\) for all \(x \in [0, 2^{64})\). You need to process \(n\) operations. In each operation, you are given a pair \((x, y)\). First, output the current value of \(f(x)\); then update \(f(x)\) to \(y\).

inputFormat

The first line contains a single integer \(n\) \( (1 \le n \le 10^5)\), representing the number of operations.

Each of the following \(n\) lines contains two unsigned 64-bit integers \(x\) and \(y\) separated by a space.

outputFormat

For each operation, output the value of \(f(x)\) before it is updated. Each output should be on a new line.

sample

3
0 5
0 7
5 10

0
5
0