Minimum Stamina to Find Friend

Xiaoming wants to visit his friend but he only knows that his friend lives in a specific unit of a building. The unit has \( n \) floors and \( m \) rooms on each floor. The rooms are numbered consecutively from 1 to \( n \times m \) such that the rooms on floor \( i \) are numbered from \( (i-1)\times m+1 \) to \( i\times m \) (for \( i = 1,2,\ldots,n \)).

His friend lives in room \( t \) (\( 1\le t \le n\times m \)). Xiaoming can choose any room on the first floor as the starting point (i.e. any room from 1 to \( m \)). In each visited room, if he finds his friend (i.e. the current room number equals \( t \)) then the search stops. Otherwise, the occupant will give him a pointer \( p \) (an integer representing the next room number) and he follows that to continue his search.

Whenever Xiaoming moves from a room with number \( i \) to the next room with number \( j \), let \( f(i) = \left\lfloor \frac{i-1}{m} \right\rfloor + 1 \) be the floor number of room \( i \). If \( f(j) > f(i) \) (i.e. he goes to an upper floor), he consumes stamina equal to \( (f(j)-f(i))\times v \) (in other words, each floor climbed costs \( v \) stamina units). Moving on the same floor or moving to a lower floor does not consume any stamina.

Note that it is possible that following the pointers leads to a cycle and Xiaoming might never find his friend. Your task is to choose the best starting room (from the first floor) such that the total stamina cost to eventually reach room \( t \) is minimized. If none of the starting rooms can eventually reach his friend, output impossible.

Input format details (see below) include all necessary information to simulate his search.

inputFormat

The input consists of:

• The first line contains three integers \( n \), \( m \), and \( v \) separated by spaces.
• The second line contains an integer \( t \) (\( 1 \le t \le n\times m \)): the room number where his friend lives.
• Then follow \( n\times m \) lines. The \( i^{th} \) of these lines corresponds to room \( i \). For a room \( i \) that is not the friend room (i.e. \( i \neq t \)), the line contains an integer \( p \) (\( 1 \le p \le n\times m \)) indicating the room to go next if the occupant is not his friend. If \( i = t \), the corresponding line can be ignored (but it will still be present in the input).

You may assume that the input is valid.

outputFormat

Output a single line containing the minimum total stamina cost required to find the friend. If it is impossible for any starting room on the first floor to eventually lead to room \( t \), output impossible.

sample

3 3 2
5
4
3
6
5
0
5
7
9
8

2