Bloxorz Rescue

After a great disaster, the Academy has not admitted any new students for many years. This year, however, the new student admission test has a milestone significance. As the top information expert at the Academy, your task is to solve the following problem inspired by the famous Bloxorz game.

The game is played on an infinite board with a designated hole located at \( (0,0) \). A 1×1 hole and a block of dimensions 2×1×1 (i.e. a rectangular prism) are given. The block may be either standing (vertical) or lying (covering two adjacent cells). When the block is lying, it can be oriented in one of two ways:

• If the block is parallel to the x-axis, it covers cells \( (x, y) \) and \( (x, y+1) \).
• If the block is parallel to the y-axis, it covers cells \( (x, y) \) and \( (x+1, y) \).

A move (or a "step") consists of rolling the block over one of its edges. However, the block must always remain in contact with the board.

The moves follow these rules. We represent a state as two cell coordinates \( (r_1, c_1) \) and \( (r_2, c_2) \). Note that if the block is standing, \( r_1 = r_2 \) and \( c_1 = c_2 \). Otherwise, if it is lying:

• Horizontal lying (parallel to the x-axis): \( r_1 = r_2 \) and \( |c_1-c_2| = 1 \).
• Vertical lying (parallel to the y-axis): \( c_1 = c_2 \) and \( |r_1-r_2| = 1 \).

If the block is standing at \( (r, c) \), then the moves are:

• Up: becomes vertical lying with cells \( (r-2, c) \) and \( (r-1, c) \).
• Down: becomes vertical lying with cells \( (r+1, c) \) and \( (r+2, c) \).
• Left: becomes horizontal lying with cells \( (r, c-2) \) and \( (r, c-1) \).
• Right: becomes horizontal lying with cells \( (r, c+1) \) and \( (r, c+2) \).

If the block is horizontal lying (covering \( (r, c) \) and \( (r, c+1) \)), then:

• Up: moves to \( (r-1, c) \) and \( (r-1, c+1) \) (remains horizontal lying).
• Down: moves to \( (r+1, c) \) and \( (r+1, c+1) \) (remains horizontal lying).
• Left: rolls to become standing at \( (r, c-1) \).
• Right: rolls to become standing at \( (r, c+2) \).

If the block is vertical lying (covering \( (r, c) \) and \( (r+1, c) \)), then:

• Left: moves to \( (r, c-1) \) and \( (r+1, c-1) \) (remains vertical lying).
• Right: moves to \( (r, c+1) \) and \( (r+1, c+1) \) (remains vertical lying).
• Up: rolls to become standing at \( (r-1, c) \).
• Down: rolls to become standing at \( (r+2, c) \).

The goal is to roll the block into the hole at \( (0,0) \) when the block is in the standing state. Determine the minimum number of steps required.

Input Format: See below.

inputFormat

The input consists of a single line with three integers:

1. x and y: the starting coordinates.
2. state: the initial state of the block, where
• 0 indicates the block is standing at \( (x,y) \).
• 1 indicates the block is lying horizontally (parallel to the x-axis) occupying \( (x,y) \) and \( (x, y+1) \).
• 2 indicates the block is lying vertically (parallel to the y-axis) occupying \( (x,y) \) and \( (x+1, y) \).

It is guaranteed that the board is infinite.

outputFormat

Output a single integer — the minimum number of steps required to roll the block into the hole at \( (0,0) \) with the block standing.

sample

0 0 0

0