A simple model for heat diffusion in 2-dimensional space, splits it up into n_x times n_x small boxes. In each time step, the temperature h(i,j) of a box with coordinates i and j is updated as

h(i,j) + c * ( (h(i-1,j) + h(i+1,j) + h(i,j-1) + h(i,j+1))/4 - h(i,j) )

where c is a diffusion constant. We consider the case of bounded region of box shape whose boundary has constant temperature 0.

Implementation

Implement in C using the GPU via OpenCL a program called diffusion that

  1. Reads array size and initial values from a text file called "init".
  2. Executes a given number of steps of heat diffusion with given diffusion constant, and
  3. Outputs the average of temperatures, say X, as average: X.
  4. Outputs the average absolute difference of each temperature to the average of all temperatures, say Y, as average absolute difference: Y.

To limit the scope of this assignments, we will not be concerned much with numerical accuracy.

Your program should accept command line arguments

./diffusion -n20 -d0.02

to compute 20 iterations with diffusion constant 0.02. You may only use OpenCL parallelism.

Input

The first row of the input file diffusion contains two positive integers, which you may assume are positive. They determine the width and the height. Each line after the first one contains three entries, two integer values that denoted valid coordinates and an initial value that parses as a floating point number. For example,

3 3
1 1 1e6

yields the setup in the following example.

Output

Since rounding errors in GPU calculations depend heavily on implementation details, a tolerance of 20% while generous is not unreasonable.

Example

As an example, we consider the case of 3 times 3 with initial values as below.
000
01,000,0000
000

Computing with diffusion constant 1/30, the next two iterations are
083330
83339667e28333
083330

and
138.91611e1138.9
1611e19347e21611e1
138.91611e1138.9

In particular, the average temperature is 111080 (as opposed to the original average 111111).

The absolute difference of each temperature and the average is
1109e29497e11109e2
9497e18236e29497e1
1109e29497e11109e2

with average is 183031.55. After five further iterations this will decrease to 151816.97.

For instance, invoking the program diffusion in the presence of a suitable init file, we expect the out

./diffusion -n2 -d0.03333
average: 111080.257812
average absolute difference: 183032.984375