Description

Elfnt just walked into an all-you-can-eat vegan buffet, represented by an grid. Each cell holds a food tray with a certain amount of fresh salad leaves. Initially, Elfnt starts at position (0-indexed) and is eager to eat as much as possible!

Elfnt can smell trays within a Manhattan distance of at most from his current position. He greedily eats according to the following rules:

1. Elfnt completely cleans out the salad tray at his current position, adding its leaves to his total. The amount of leaves at this cell then becomes 0 (indicating an empty plate).
2. He sniffs around and moves to the tray within Manhattan distance that has the greatest amount of leaves. If all reachable trays within distance contain 0 leaves, Elfnt stops moving and eating immediately.

Note:

• The Manhattan distance between two cells and is defined as .

Input

The first line contains three integers , , and — the number of rows, the number of columns, and the maximum Manhattan distance Elfnt can smell.
The next lines each contain integers, representing the initial amount of leaves on each tray.
The last line contains two integers and , representing Elfnt's starting row and column coordinates.

Constraints

• The initial amount of leaves on any tray satisfies .
• All non-zero leaf amounts are guaranteed to be distinct (i.e., except for trays with 0 leaves, all leaf values across the buffet are unique).

Output

Output a single integer representing the total amount of salad leaves Elfnt consumes before he stops, followed by a new line.

Sample Input  Download

Sample Output  Download

Discuss

Description

Elfnt and his family (a total of elephants) are claiming their own territories. We can represent the land as a 1D coordinate line. Each elephant chooses a continuous segment as its territory, starting from position to (inclusive interval ).

An elephant A's territory completely contains elephant B's territory if and .

Your task is to analyze the overlapping territories. For each elephant, determine if its territory contains at least one other elephant's territory, and if its territory is contained by at least one other elephant's territory.

Input

The first line contains a single integer — the number of elephants.
The following lines each contain two integers and , representing the starting and ending points of an elephant's territory.
(Note: The elephants are numbered from to in the order they appear in the input).

Constraints

• All given territories are guaranteed to be distinct.

Output

The first line should contain integers. The -th integer should be 1 if the -th elephant's territory completely contains at least one other territory, and 0 otherwise.
The second line should contain integers. The -th integer should be 1 if the -th elephant's territory is completely contained by at least one other territory, and 0 otherwise.

For both lines, consecutive integers must be separated by a space. There must be no space after the last integer of each line, and each line must end with a newline.

Sample Input  Download

Sample Output  Download

Discuss

Description

RedCapeFlyingCat is standing at coordinate on a number line and wants to reach the goal at coordinate .

There is a wall at coordinate . At first, RedCapeFlyingCat cannot pass through coordinate . There is also a hammer at coordinate : once RedCapeFlyingCat arrives at coordinate , the hammer is picked up, and from then on the wall can be broken and passed through.

Determine whether RedCapeFlyingCat can reach the goal. If so, find the minimum total distance that has to be traveled.

Explanation

In the sample test case, , , and . The wall is farther away than the goal, so it is not in the way: RedCapeFlyingCat goes straight from to . The total distance is .

Two more examples (they are not given as sample test cases):

• , , : the wall blocks the way to the goal. RedCapeFlyingCat first goes from to to pick up the hammer (distance ), then goes from to , breaking the wall on the way (distance ). The total distance is .
• , , : the wall blocks the way to the goal, and it also blocks the way to the hammer. The goal cannot be reached, so the answer is -1.

Input

Three lines, each with one integer:

• Line 1: , the coordinate of the goal
• Line 2: , the coordinate of the wall
• Line 3: , the coordinate of the hammer

Constraints

• , and
• , , and are distinct
• All input values are integers

Output

One line containing one integer: the minimum total distance RedCapeFlyingCat has to travel to reach the goal.

If the goal cannot be reached, output -1.

Sample Input  Download

Sample Output  Download

Discuss