There are N cities (numbered from 1 to N, from left to right) arranged in a row and N-1 one-way roads between them: 1→2→3→...→N-1→N. The government has a plan to build M new roads. The roads will be built one by one. The K-th road will connect the A[K]-th city with the B[K]-th city (roads are numbered from 0 to M-1). Each road will lead from the left to the right, from a city with a smaller number to a city with a larger number. No two roads will intersect. Formally, there will be no two roads A→B and C→D, such as A

Jack lives in city number 1 and his school is located in city number N. He wants to know the distance from home to school after each new road is built.

Write a function: class Solution { public int[] solution(int[] A, int[] B, int N); }

that, given two arrays A, B consisting of M integers each and an integer N, returns an array D consisting of M integers, where D[K] denotes the distance from home to school after building the first K roads. The distance is the minimum number of roads required to move between two cities.

Examples:

1. Given A=[2,5,1], B=[4,7,4] and N=7, the function should return [5,4,3]. After building the first road (2→4), the shortest path from home to school is: 1→2→4→5→6→7, and its length is 5. After building the second road (5→7), the shortest path from home to school is: 1→2→4→5→7, and its length is 4. After building the third road (1→4), the shortest path from home to school is: 1→4→5→7, and its length is 3.

2. Given X=[1,1,1], Y=[7,4,6] and N=7, the function should return [1,1,1]. After building the first road (1→7), the length of the shortest path from home to school is 1. The roads built subsequently do not improve the result.

3. Given X=[30,50,40], Y=[40,60,50] and N=7, the function should return [90,81,72]. Each new road shortens the distance from home to school by 9.

Write an efficient algorithm for the following assumptions:

- N is an integer within the range [1..100000];

- M is an integer within the range [0..100000];

- each element of arrays A and B is an integer within the range [1..N]; - A[K] < B[K] for each K within the range [0..M-1];

- A and B have the same length;

- there are no two identical roads;

- there are no two intersection roads.