Transforming Robot

Interview

Time limit1sMemory limit128 MB

Summary

Given N digit strings of equal length, move between states with cost equal to the sum of squared digit differences per position, and find the minimum cost from a start state to a target state.

Level: Medium6 of 10
Topics: Graph, Shortest path, Implementation, Math
Solved: No attempts yet

Problem

Seunggyun is obsessed with transforming robots. People say that someone who takes one field to the extreme ends up understanding the world through it, and that is exactly Seunggyun. Watching people whose feelings change from moment to moment, he decided that a person is the same as a transforming robot. He also believed that the flow of the world is one huge transforming robot being assembled, and that our role inside it is to be a part that meshes correctly with the other parts. His teacher Junha, who had been watching all this, was not happy. He had shown Seunggyun transforming robots to get him interested in science and math, but Seunggyun was becoming a philosopher instead. Junha could not take it any longer and bolted a coin slot onto the robot.

From now on the robot transforms only when you feed it a coin. The shape of a part can be written as a single digit, and a transformation state of the robot is the string of those digits in order. Every state is written with the same length. Transforming directly from one state to another costs the sum of the squared differences of the two digits in each matching position. For example, transforming $123$ into $222$ costs $(1-2)^2 + (2-2)^2 + (3-2)^2 = 2$ .

The robot may pass through other transformation states on the way, and it pays the cost of every transformation it makes. Seunggyun is hopeless at math, so find for him the minimum amount of money that turns the current state into the state he wants.

Input

The first line contains the number of transformation states $N$ . ( $1 \le N \le 1000$ )

Each of the next $N$ lines contains one transformation state, written as a string of digits. A state is at most $100$ digits long, every state has the same length, and a state may start with $0$ .

The last line contains the number of the current transformation state and the number of the state Seunggyun wants, separated by a space. States are numbered from $1$ in the order they were given. The two numbers may be equal.

Output

Print the minimum amount of money needed to turn the current state into the state Seunggyun wants.

Examples3

Example 1
Input
```
3
11
33
55
1 3
```
Expected output
```
16
```
Example 2
Input
```
1
7
1 1
```
Expected output
```
0
```
Example 3
Input
```
5
0
2
4
6
8
1 5
```
Expected output
```
16
```