Minimum Data Transmission Time

In a 2D Cartesian coordinate system, there are k CPUs labeled from \(1\) to \(k\). The position of each CPU is given by its integer coordinates \((x_i, y_i)\) satisfying \(1 \le x_i \le n\) and \(1 \le y_i \le m\). It is guaranteed that CPU 1 is at \((1,1)\) and CPU \(k\) is at \((n,m)\).

The time cost to transmit data from CPU \(i\) at \((x_i, y_i)\) to CPU \(j\) at \((x_j, y_j)\) is defined as \[ 2^{\max(|x_i-x_j|,\,|y_i-y_j|)} \] units of time. Your task is to find the minimum total time required to send the data from CPU 1 to CPU \(k\) and output one corresponding transmission scheme (i.e. the sequence of CPU IDs along the path).

inputFormat

The first line contains three integers (n), (m), and (k) (the grid dimensions and the number of CPUs). Each of the following (k) lines contains two integers (x_i) and (y_i), representing the coordinates of CPU (i). It is guaranteed that CPU 1 is at (1,1) and CPU (k) is at (n,m).

outputFormat

The output should contain three parts. In the first line, output the minimum total transmission time. In the second line, output an integer (p) representing the number of CPUs in the chosen transmission scheme. In the third line, output (p) space-separated integers denoting the sequence of CPU IDs (starting with 1 and ending with (k)) along the path that achieves the minimum time.

sample

3 3 3
1 1
2 2
3 3

4
2
1 3