Description

There are  black points on coordinate plane. The -th black point(they're numbered in 1-based) is on  in the beginning.

Then  events happens. There are two types of event:

1. y-coordinates of the -th point increase by . The -th point must exist on coordinate plane.
2. a blue point appears on  and it will keep moving right until it reaches . When it touches some black point, that black point will vanish. The blue point will vanish when it touches a black point or stop moving.

In the end, output y-coordinates of all the black points.

Input

The first line contains two integers  and   – the number of black points and the number of events.

Then  lines follow. The -th line contains an integer  – the type of the -th event. If  is equal to 1, then two integers  and  follow(the -th point must exist on coordinate plane). Otherwise three integers  and  follow.

 

It's guaranteed that:

• The 1st testcase must be identical to the Sample below
• For the first 5 testcases:  and  y-coordinate of any black point  always holds
• For the first 7 testcases:  y-coordinate of any black point  always holds

Output

After the  events, output y-coordinates of all the black points and print a newline('\n') character. If some black point doesn't exist, output -1 instead of its y-coordinate.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There is a  grid. Each cell  contains exactly one integer .

You are on  in the beginning and want to go to .

You could move to an adjacent cell if the integer of it is greater than or equal to the integer of the cell which you are on. An adjacent cell is a cell which shares a common side with the cell which you are on.

Find the minimum number of cells you need to pass by to reach . There may be no such a path for you to reach .

Input

The first line contains two positive integers  and  – the size of the grid.

Then  lines folllow. The -th line contains  integers. The -th integer in the -th line  is the integer of the cell .

The next line contains two integers  and  – the initial cell you are on.

The final line contains two integers  and  – the cell you want to go.

Note that  and  must be different(i.e  or ).

 

It's guaranteed that:

• The 1st testcase must be identical to the Sample #1 below
• For the first 6 testcases:  and 

Output

Output the minimum cells you must pass by for you to reach . Output -1 instead if there is no such a path.

Remember to print a newline('\n') character at the end of the line.

 

Note: there are two sample below. "# Sample Input 1/2/3" and "# Sample Output 1/2/3" are not the part of input and output.

They are just for marking that the following content corresponds to which sample.

Sample Input  Download

Sample Output  Download

Tags

Discuss